$$\Huge版权声明$$
原作者为 Conan15。
$$\Huge转载请注明出处。$$
$$\Huge 二帖传送门$$
温馨提示：此题解适合人群为算法学习者，不那么适合语法基础课还没学完的学生，对于初学者，建议看看yxc视频
为了不误导初学者
先放一波正常代码：
/*
A K K CCCCCCCCCCCC SSSSSSSSSSS PPPPPPPPPPPPP
A A K K C S P P
A A K K C S P P
A A K K C S P P
A A K K C SSSSSSSSSSS PPPPPPPPPPPPP
AAAAAAAAAAA K K C S P
A A K K C S P
A A K K C S P
A A K K CCCCCCCCCCC SSSSSSSSSSS P
A K K IIIIIIIIIII OOOOOOOOOOO IIIIIIIIIII
A A K K I O O I
A A K K I O O I
A A K K I O O I
A A K K I O O I
AAAAAAAAAAA K K I O O I
A A K K I O O I
A A K K I O O I
A A K K IIIIIIIIIII OOOOOOOOOOO IIIIIIIIIII
*/
#include <bits/stdc++.h>
using namespace std;
int a, b; //定义两个整型变量a和b
int main() {
scanf("%d%d", &a, &b); //读入a和b，当然用cin也没毛病
printf("%d\n", a + b); //输出a+b，当然用cout也没毛病
return 0;
}
首先声明此题非常困（jian）难（dan），连国（ru）家（men）队（cai）员（niao）都做不（de）出，我想了1年（miao）才（jiu）把这题想出来了。
$\Huge此帖强烈建议收藏$
祝
点赞的童鞋们！
身体健康万事如意周赛AK题解爆赞期末考试全科满分！
搞恶！
搞恶！
非常搞恶！
是不是只有我把这道题标注成困难啊……
A+B尝试代码快捷键点这里！！！！！！
在各位大佬的建议下，我又写了这个帖子hhh……
前方高能！！！警告！！！
本文长度恐怖！比上次还恐怖！请各位大佬蒟蒻们小心！
建议慢慢食用
求
赞
求
赞
求
赞
y总一定全看得懂……
其实有四五个算法是查的，完全看不懂……
算法一、DFS一号
#include <bits/stdc++.h>
using namespace std;
int n = 2, a[5], s;
int dfs(int x, int sum) {
if (x > n) return sum;
int i = dfs(x + 1, sum);
int j = dfs(x + 1, sum + a[x]);
if (i == s) return i;
if (j == s) return j;
return -1;
}
int main() {
for (int i = 1;i <= n; i++) scanf("%d", &a[i]), s += a[i];
cout << dfs(1, 0) << endl;
return 0;
}
算法二、DFS二号
#include <bits/stdc++.h>
using namespace std;
int a, b;
int dfs(int x) {
if (x <= 5) return x;
return dfs(x / 2) + dfs(x - x / 2);
}
int main() {
scanf("%d%d", &a, &b);
printf("%d\n", dfs(a) + dfs(b));
return 0;
}
算法三、BFS
#include <bits/stdc++.h>
using namespace std;
int n = 2, a[5], s;
queue<int> q;
void bfs() {
q.push(0);
int c = 0;
while (q.size()) {
c++;
int f = q.front(); q.pop();
if (f == s) {printf("%d\n", f); exit(0);}
q.push(f + a[c]);
q.push(f);
}
}
int main() {
for (int i = 1;i <= n; i++) scanf("%d", &a[i]), s += a[i];
bfs();
return 0;
}
算法四、直接算咯
#include <bits/stdc++.h>
using namespace std;
int a, b;
int main() {
scanf("%d%d", &a, &b);
printf("%d\n", a + b);
return 0;
}
算法五、二分
#include <bits/stdc++.h>
using namespace std;
int a, b;
int main() {
scanf("%d%d", &a, &b);
int l = 0, r = 200000000;
while (l < r) {
int mid = l + r >> 1;
if (mid == a + b) {printf("%d\n", mid); return 0;}
if (mid < a + b) l = mid + 1;
if (mid > a + b) r = mid - 1;
}
cout << l << endl;
return 0;
}
算法六、稍微有点暴力的枚举
但是还是$1892ms$卡过了欸
#include <bits/stdc++.h>
using namespace std;
int a, b;
int main() {
scanf("%d%d", &a, &b);
for (int i = 0;i <= 200000000; i++) if (a + b == i) {printf("%d\n", i); break;}
return 0;
}
算法七、最短路之dijkstra
思路：定义节点1到节点2路径长度为a，节点2到节点3路径长度为b
则答案为节点1到节点3的最短路（也就是$a+b$）
#include <bits/stdc++.h>
using namespace std;
int w[5][5], d[5], v[5];
int n = 3;
void dijkstra() {
memset(d, 0x3f, sizeof d);
memset(v, 0, sizeof v);
d[1] = 0;
for (int i = 1;i < n; i++) {
int x = 0;
for (int j = 1;j <= n; j++)
if (!v[j] && (x == 0 || d[j] < d[x])) x = j;
v[x] = 1;
for (int y = 1;y <= n; y++)
d[y] = min(d[y], d[x] + w[x][y]);
}
}
int main() {
int a, b; scanf("%d%d", &a, &b);
memset(w, 0x3f, sizeof w);
w[1][2] = a; w[2][3] = b;
dijkstra();
printf("%d\n", d[3]);
return 0;
}
算法八、最短路之SPFA
思路同上
#include <bits/stdc++.h>
using namespace std;
int a, b, n = 3;
int w[5][5], d[5], v[5];
queue<int> q;
void spfa() {
memset(d, 0x3f, sizeof d);
memset(v, 0, sizeof v);
d[1] = 0, v[1] = 1;
q.push(1);
while (q.size()) {
int x = q.front(); q.pop();
v[x] = 0;
for (int i = 1;i <= n; i++) {
// if (w[x][i] == 0x3f) continue;
if (d[i] > d[x] + w[x][i]) {
d[i] = d[x] + w[x][i];
if (!v[i]) q.push(i), v[i] = 1;
}
}
}
}
int main() {
scanf("%d%d", &a, &b);
memset(w, 0x3f, sizeof w);
w[1][2] = a; w[2][3] = b;
spfa();
printf("%d\n", d[3]);
return 0;
}
算法九、最短路之Floyd
思路同上
#include <bits/stdc++.h>
using namespace std;
int d[5][5], n = 3;
int main() {
int a, b; scanf("%d%d", &a, &b);
memset(d, 0x3f, sizeof d);
d[1][2] = a; d[2][3] = b;
for (int k = 1;k <= n; k++)
for (int i = 1;i <= n; i++)
for (int j = 1;j <= n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
printf("%d\n", d[1][3]);
return 0;
}
算法十、高精
#include<bits/stdc++.h>
using namespace std;
string a0, b0;
int a[1005], b[1005];
int main(){
cin >> a0 >> b0;
int l1 = a0.size(), l2 = b0.size();
for (int i = 0;i < l1; i++) a[l1 - i] = a0[i] - 48;
for (int i = 0;i < l2; i++) b[l2 - i] = b0[i] - 48;
l1 = max(l1, l2);
for (int i = 1;i <= l1; i++) {
a[i] += b[i];
if (a[i] > 9) a[i + 1] += 1, a[i] %= 10;
}
if (a[max(l1, l2) + 1] > 0) l1++;
for (int i = l1;i >= 1; i--) printf("%d", a[i]);
return 0;
}
算法十一、最小生成树之kruskal
思路其实和最短路的一样，只是改成用最小生成树的方法求罢了
#include <bits/stdc++.h>
using namespace std;
struct rec {
int x, y, z;
} edge[5];
int fa[5], m = 2, ans = 0;
int get(int x) {
if (x == fa[x]) return x;
return fa[x] = get(fa[x]);
}
int cmp(rec a, rec b) { return a.z < b.z; }
int main() {
int a, b; scanf("%d%d", &a, &b);
edge[1] = (rec){1, 2, a};
edge[2] = (rec){2, 3, b};
for (int i = 1;i <= m + 1; i++) fa[i] = i;
sort(edge + 1, edge + 1 + m, cmp);
for (int i = 1;i <= m; i++) {
int x = get(edge[i].x);
int y = get(edge[i].y);
if (x == y) continue;
fa[x] = y;
ans += edge[i].z;
}
printf("%d\n", ans);
return 0;
}
算法十二、最小生成树之prim
思路同上
#include <bits/stdc++.h>
using namespace std;
int w[5][5], d[5], n = 3, ans, v[5];
void prim() {
memset(d, 0x3f, sizeof d);
memset(v, 0, sizeof v);
d[1] = 0;
for (int i = 1;i < n; i++) {
int x = 0;
for (int j = 1;j <= n; j++)
if (!v[j] && (x == 0 || d[j] < d[x])) x = j;
v[x] = 1;
for (int y = 1;y <= n; y++)
if (!v[y]) d[y] = min(d[y], w[x][y]);
}
}
int main() {
int a, b; scanf("%d%d", &a, &b);
memset(w, 0x3f, sizeof w);
w[1][2] = a; w[2][3] = b;
prim();
int ans = 0;
for (int i = 2;i <= n; i++) ans += d[i];
printf("%d\n", ans);
return 0;
}
算法十三、前缀和
#include <bits/stdc++.h>
using namespace std;
int a[5], s[5];
int main() {
for (int i = 1;i <= 2; i++) scanf("%d", &a[i]), s[i] += a[i] + s[i - 1];
printf("%d\n", s[2]);
return 0;
}
算法十四、后缀和
#include <bits/stdc++.h>
using namespace std;
int a[5], s[5];
int main() {
for (int i = 2;i >= 1; i--) scanf("%d", &a[i]), s[i] += a[i] + s[i + 1];
printf("%d\n", s[1]);
return 0;
}
算法十五、位运算
#include <bits/stdc++.h>
using namespace std;
int add(int a, int b) {
if (b == 0) return a;
return add(a ^ b, (a & b) << 1);
}
int main() {
int a, b; scanf("%d%d", &a, &b);
printf("%d\n", add(a, b));
return 0;
}
算法十六、树的直径——BFS
emmm……思路继续和最短路的一样。。。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int head[maxn * 2],edge[maxn * 2],Next[maxn * 2],ver[maxn * 2];
int vis[maxn], dist[maxn];
int n = 3, p, q, d;
int tot = 0;
int maxd = 0;
void add(int u,int v,int w) {
ver[ ++ tot] = v,edge[tot] = w;
Next[tot] = head[u],head[u] = tot;
}
int BFS(int u) {
queue<int>Q;
while(!Q.empty()) Q.pop();
memset(vis, 0, sizeof vis);
memset(dist, 0, sizeof dist);
Q.push(u);
int x, max_num = 0;
while(!Q.empty()) {
x = Q.front();
Q.pop();
vis[x] = 1;
for(int i = head[x]; i ; i = Next[i]) {
int y = ver[i];
if(vis[y]) continue;
vis[y] = 1;
dist[y] = dist[x] + edge[i];
if(dist[y] > maxd) {
maxd = dist[y];
max_num = y;
}
Q.push(y);
}
}
return max_num;
}
int main(void) {
int a, b; scanf("%d%d", &a, &b);
add(1, 2, a); add(2, 1, a);
add(2, 3, b); add(3, 2, b);
BFS(BFS(1));
int ans = 0;
for (int i = 1;i <= n; i++) ans = max(ans, dist[i]);
printf("%d\n", ans);
return 0;
}
算法十七、树的直径——DFS
思路同上
#include<bits/stdc++.h>
#define maxn 100000
using namespace std;
struct node {
int u, v, w, nex;
} edge[2 * maxn + 10];
int n = 3, d[maxn + 10], head[maxn + 10], f_num, cnt = 0, ans;
inline void add(int x,int y,int z) {
edge[++cnt].u = x;
edge[cnt].v = y;
edge[cnt].w = z;
edge[cnt].nex = head[x];
head[x] = cnt;
}
inline void dfs(int x, int fa) {
if(ans < d[x]) {
ans = d[x];
f_num = x;
}
for (int i = head[x]; i != -1; i = edge[i].nex) {
int j = edge[i].v;
if (j == fa)continue;
d[j] = d[x] + edge[i].w;
dfs(j, x);
}
}
int main() {
memset(head, -1, sizeof(head));
int a, b; scanf("%d%d", &a, &b);
add(1, 2, a); add(2, 1, a);
add(2, 3, b); add(3, 2, b);
dfs(1, 0);
ans = 0;
d[f_num] = 0;
dfs(f_num, 0);
for (int i = 1;i <= n; i++) ans = max(ans, d[i]);
printf("%d", ans);
return 0;
}
算法十八、树的直径——树形DP
还是一样咯
#include <bits/stdc++.h>
using namespace std;
int f[5], n = 3, cnt, h[5], ans, dis[5];
struct edge {
int to, next, vi;
} e[5];
void add(int u, int v, int w) {
e[cnt].to= v;
e[cnt].vi = w;
e[cnt].next = h[u];
h[u] = cnt++;
}
void dp(int u, int fa) {
for (int i = h[u]; ~i; i = e[i].next) {
int v = e[i].to;
if (v == fa) continue;
dp(v, u);
ans = max(ans, dis[v] + dis[u] + e[i].vi);
dis[u] = max(dis[u], dis[v] + e[i].vi);
}
}
int main() {
memset(h, -1, sizeof h);
int a, b; scanf("%d%d", &a, &b);
add(1, 2, a); add(2, 1, a);
add(2, 3, b); add(3, 2, b);
dp(1, 0);
printf("%d\n", ans);
return 0;
}
算法十九、网络流
从别的大佬那边搞过来的，但是一点都看不懂┭┮﹏┭┮
#include<bits/stdc++.h>
using namespace std;
#define set(x) Set(x)
#define REP(i,j,k) for (int i=(j),_end_=(k);i<=_end_;++i)
#define DREP(i,j,k) for (int i=(j),_start_=(k);i>=_start_;--i)
#define mp make_pair
#define x first
#define y second
#define pb push_back
template<typename T> inline bool chkmin(T &a,const T &b){ return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a,const T &b){ return a < b ? a = b, 1 : 0; }
typedef long long LL;
typedef pair<int,int> node;
const int dmax = 1010, oo = 0x3f3f3f3f;
int n, m;
int a[dmax][dmax] , ans;
int d[dmax], e[dmax];
priority_queue <node> q;
inline bool operator >(node a,node b){ return a.y>b.y; }
bool p[dmax];
void Set(int x){ p[x] = 1; }
void unset(int x){ p[x] = 0; }
bool check(int x){ return x != 1 && x != n && !p[x] && e[x] > 0; }
void preflow(){
e[1] = oo;
d[1] = n - 1;
q.push(mp(1, n - 1));
set(1);
while (!q.empty()) {
bool flag = 1;
int k = q.top().x;
q.pop(), unset(k);
DREP(i, n, 1)
if ((d[k] == d[i] + 1 || k == 1) && a[k][i] > 0){
flag = 0;
int t = min(a[k][i], e[k]);
e[k] -= t;
a[k][i] -= t;
e[i] += t;
a[i][k] += t;
if (check(i)) {
q.push(mp(i, d[i]));
set(i);
}
if (e[k] == 0) break;
}
if (flag) {
d[k] = oo;
REP(i, 1, n)
if (a[k][i] > 0) chkmin(d[k], d[i] + 1);
}
if (check(k)) {
q.push(mp(k, d[k]));
set(k);
}
}
ans = e[n];
}
int main() {
n = 2, m = 2;
int x, y;
scanf("%d%d", &x, &y);
a[1][2] += x + y;
preflow();
printf("%d\n", ans);
return 0;
}
算法二十、线段树
转化为区间求和问题
#include <bits/stdc++.h>
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define add(x) tree[x].add
using namespace std;
struct SegmentTree {
int l, r; //区间左右端点
long long sum, add; //sum 区间和 add 延迟标记
} tree[400010];
int a[100010], n = 1, m = 2;
void build (int p, int l, int r) {
l(p) = l, r(p) = r;
if(l == r) {sum(p) = a[l]; return;}
int mid = l + r >> 1;
build(p * 2, l, mid);
build(p * 2 + 1, mid + 1, r);
sum(p) = sum(p * 2) + sum(p * 2 + 1);
}
void spread(int p) {
if(add(p)) { //节点p有标记
sum(p * 2) += add(p) * (r(p * 2) - l(p * 2) + 1); //更新左子节点信息
sum(p * 2 + 1) += add(p) * (r(p * 2 + 1) - l(p * 2 + 1) + 1); //更新右子节点
add(p * 2) += add(p); //给左子节点打延迟标记
add(p * 2 + 1) += add(p); //给右子节点打延迟标记
add(p) = 0; //清除p的标记
}
}
void change(int p, int l, int r, int d) {
if(l <= l(p) && r >= r(p)) { //完全覆盖
sum(p) += (long long) d * (r(p) - l(p) + 1); //更新节点信息
add(p) += d; //给节点打延迟标记
return;
}
spread(p); //下传延迟标记
int mid = l(p) + r(p) >> 1;
if(l <= mid) change(p * 2, l, r, d);
if(r > mid) change(p * 2 + 1, l, r, d);
sum(p) = sum(p * 2) + sum(p * 2 + 1);
}
long long ask(int p, int l, int r) {
if(l <= l(p) && r >= r(p)) return sum(p);
spread(p);
int mid = l(p) + r(p) >> 1;
long long val = 0;
if(l <= mid) val += ask(p * 2, l, r);
if(r > mid) val += ask(p * 2 + 1, l, r);
return val;
}
int main() {
a[1] = 0;
build(1, 1, n);
while(m--) {
int d = 0;
scanf("%d", &d);
change(1, 1, 1, d);
}
printf("%lld\n", ask(1, 1, 1));
return 0;
}
算法二十一、树状数组
思路一样，区间求和
#include<bits/stdc++.h>
using namespace std;
const int SIZE = 100010;
int a[SIZE], n = 1, m = 2;
long long c[2][SIZE], sum[SIZE];
long long ask(int k, int x) {
long long ans = 0;
for(; x ; x -= x & -x) ans += c[k][x];
return ans;
}
void add(int k,int x,int y) {
for(; x <= n; x += x & -x) c[k][x] += y;
}
int main() {
a[1] = 0;
while(m--) {
int d = 0;
scanf("%d", &d);
add(0, 1, d);
add(0, 2, -d);
add(1, 1, d);
add(1, 2, -2 * d);
}
long long ans = sum[1] + 2 * ask(0, 1) - ask(1, 1);
ans -= sum[0] + 1 * ask(0, 0) - ask(1, 0);
printf("%lld\n", ans);
return 0;
}
算法二十二、分块
思路一样，区间求和
#include<bits/stdc++.h>
using namespace std;
long long a[50000010], sum[50000010], add[50000010];
int L[50000010], R[50000010];
int pos[50000010];
int n = 1, m = 2, t;
void change(int l, int r, long long d) {
int p = pos[l], q = pos[r];
if (p == q) {
for (int i = l; i <= r; i++) a[i] += d;
sum[p] += d*(r - l + 1);
}
else {
for (int i = p + 1; i <= q - 1; i++) add[i] += d;
for (int i = l; i <= R[p]; i++) a[i] += d;
sum[p] += d*(R[p] - l + 1);
for (int i = L[q]; i <= r; i++) a[i] += d;
sum[q] += d*(r - L[q] + 1);
}
}
long long ask(int l, int r) {
int p = pos[l], q = pos[r];
long long ans = 0;
if (p == q) {
for (int i = l; i <= r; i++) ans += a[i];
ans += add[p] * (r - l + 1);
}
else {
for (int i = p + 1; i <= q - 1; i++)
ans += sum[i] + add[i] * (R[i] - L[i] + 1);
for (int i = l; i <= R[p]; i++) ans += a[i];
ans += add[p] * (R[p] - l + 1);
for (int i = L[q]; i <= r; i++) ans += a[i];
ans += add[q] * (r - L[q] + 1);
}
return ans;
}
int main() {
a[1] = 0;
t = sqrt(n*1.0);
for (int i = 1; i <= t; i++) {
L[i] = (i - 1)*sqrt(n*1.0) + 1;
R[i] = i*sqrt(n*1.0);
}
if (R[t] < n) t++, L[t] = R[t - 1] + 1, R[t] = n;
for (int i = 1; i <= t; i++)
for (int j = L[i]; j <= R[i]; j++) {
pos[j] = i;
sum[i] += a[j];
}
while (m--) {
int d;
scanf("%d", &d);
change(1, 1, d);
}
printf("%lld\n", ask(1, 1));
}
算法二十三、LCT
来自洛谷
#include<bits/stdc++.h>
using namespace std;
struct node
{
int data,rev,sum;
node *son[2],*pre;
bool judge();
bool isroot();
void pushdown();
void update();
void setson(node *child,int lr);
}lct[233];
int top,a,b;
node *getnew(int x)
{
node *now=lct+ ++top;
now->data=x;
now->pre=now->son[1]=now->son[0]=lct;
now->sum=0;
now->rev=0;
return now;
}
bool node::judge()
{
return pre->son[1]==this;
}
bool node::isroot()
{
if(pre==lct)return true;
return !(pre->son[1]==this||pre->son[0]==this);
}
void node::pushdown()
{
if(this==lct||!rev)return;
swap(son[0],son[1]);
son[0]->rev^=1;
son[1]->rev^=1;
rev=0;
}
void node::update()
{
sum=son[1]->sum+son[0]->sum+data;
}
void node::setson(node *child,int lr)
{
this->pushdown();
child->pre=this;
son[lr]=child;
this->update();
}
void rotate(node *now)
{
node *father=now->pre,*grandfa=father->pre;
if(!father->isroot()) grandfa->pushdown();
father->pushdown();
now->pushdown();
int lr=now->judge();
father->setson(now->son[lr^1],lr);
if(father->isroot()) now->pre=grandfa;
else grandfa->setson(now,father->judge());
now->setson(father,lr^1);
father->update();
now->update();
if(grandfa!=lct) grandfa->update();
}
void splay(node *now)
{
if(now->isroot())return;
for(; !now->isroot(); rotate(now))
if(!now->pre->isroot())
now->judge()==now->pre->judge()?rotate(now->pre):rotate(now);
}
node *access(node *now)
{
node *last=lct;
for(; now!=lct; last=now,now=now->pre) {
splay(now);
now->setson(last,1);
}
return last;
}
void changeroot(node *now)
{
access(now)->rev^=1;
splay(now);
}
void connect(node *x,node *y)
{
changeroot(x);
x->pre=y;
access(x);
}
void cut(node *x,node *y)
{
changeroot(x);
access(y);
splay(x);
x->pushdown();
x->son[1]=y->pre=lct;
x->update();
}
int query(node *x,node *y)
{
changeroot(x);
node *now=access(y);
return now->sum;
}
int main()
{
scanf("%d%d",&a,&b);
node *A=getnew(a);
node *B=getnew(b);
connect(A,B);
cut(A,B);
connect(A,B);
printf("%d",query(A,B));
return 0;
}
算法二十四、Splay
来自洛谷
#include <bits/stdc++.h>
#define ll long long
#define N 100000
using namespace std;
int sz[N], rev[N], tag[N], sum[N], ch[N][2], fa[N], val[N];
int n, m, rt, x;
void push_up(int x){
sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
sum[x] = sum[ch[x][1]] + sum[ch[x][0]] + val[x];
}
void push_down(int x){
if(rev[x]){
swap(ch[x][0], ch[x][1]);
if(ch[x][1]) rev[ch[x][1]] ^= 1;
if(ch[x][0]) rev[ch[x][0]] ^= 1;
rev[x] = 0;
}
if(tag[x]){
if(ch[x][1]) tag[ch[x][1]] += tag[x], sum[ch[x][1]] += tag[x];
if(ch[x][0]) tag[ch[x][0]] += tag[x], sum[ch[x][0]] += tag[x];
tag[x] = 0;
}
}
void rotate(int x, int &k){
int y = fa[x], z = fa[fa[x]];
int kind = ch[y][1] == x;
if(y == k) k = x;
else ch[z][ch[z][1]==y] = x;
fa[x] = z; fa[y] = x; fa[ch[x][!kind]] = y;
ch[y][kind] = ch[x][!kind]; ch[x][!kind] = y;
push_up(y); push_up(x);
}
void splay(int x, int &k){
while(x != k){
int y = fa[x], z = fa[fa[x]];
if(y != k) if(ch[y][1] == x ^ ch[z][1] == y) rotate(x, k);
else rotate(y, k);
rotate(x, k);
}
}
int kth(int x, int k){
push_down(x);
int r = sz[ch[x][0]]+1;
if(k == r) return x;
if(k < r) return kth(ch[x][0], k);
else return kth(ch[x][1], k-r);
}
void split(int l, int r){
int x = kth(rt, l), y = kth(rt, r+2);
splay(x, rt); splay(y, ch[rt][1]);
}
void rever(int l, int r){
split(l, r);
rev[ch[ch[rt][1]][0]] ^= 1;
}
void add(int l, int r, int v){
split(l, r);
tag[ch[ch[rt][1]][0]] += v;
val[ch[ch[rt][1]][0]] += v;
push_up(ch[ch[rt][1]][0]);
}
int build(int l, int r, int f){
if(l > r) return 0;
if(l == r){
fa[l] = f;
sz[l] = 1;
return l;
}
int mid = l + r >> 1;
ch[mid][0] = build(l, mid-1, mid);
ch[mid][1] = build(mid+1, r, mid);
fa[mid] = f;
push_up(mid);
return mid;
}
int asksum(int l, int r){
split(l, r);
return sum[ch[ch[rt][1]][0]];
}
int main(){
//总共两个数
n = 2;
rt = build(1, n+2, 0);//建树
for(int i = 1; i <= n; i++){
scanf("%d", &x);
add(i, i, x);//区间加
}
rever(1, n);//区间翻转
printf("%d\n", asksum(1, n));//区间求和
return 0;
}
算法二十五、LCA
来自洛谷
#include<cstdio> //头文件
#define NI 2
//从来不喜欢算log所以一般用常数 不知道算不算坏习惯 因为3个节点 所以log3(当然以2为底)上取整得2
struct edge
{
int to,next,data; //分别表示边的终点，下一条边的编号和边的权值
}e[30]; //邻接表，点少边少开30是为了浪啊
int v[10],d[10],lca[10][NI+1],f[10][NI+1],tot=0; //数组开到10依然为了浪
//数组还解释嘛，v表示第一条边在邻接表中的编号，d是深度，lca[x][i]表示x向上跳2^i的节点，f[x][i]表示x向上跳2^i的距离和
void build(int x,int y,int z) //建边
{
e[++tot].to=y; e[tot].data=z; e[tot].next=v[x]; v[x]=tot;
e[++tot].to=x; e[tot].data=z; e[tot].next=v[y]; v[y]=tot;
}
void dfs(int x) //递归建树
{
for(int i=1;i<=NI;i++) //懒，所以常数懒得优化
f[x][i]=f[x][i-1]+f[lca[x][i-1]][i-1],
lca[x][i]=lca[lca[x][i-1]][i-1]; //建树的同时进行预处理
for(int i=v[x];i;i=e[i].next) //遍历每个连接的点
{
int y=e[i].to;
if(lca[x][0]==y) continue;
lca[y][0]=x; //小技巧：lca[x][0]即为x的父亲~~（向上跳2^0=1不就是父节点嘛）
f[y][0]=e[i].data;
d[y]=d[x]+1;
dfs(y); //再以这个节点为根建子树【这里真的用得到嘛？？】
}
}
int ask(int x,int y) //询问，也是关键
{
if(d[x]<d[y]) {int t=x;x=y;y=t;} //把x搞成深的点
int k=d[x]-d[y],ans=0;
for(int i=0;i<=NI;i++)
if(k&(1<<i)) //若能跳就把x跳一跳
ans+=f[x][i], //更新信息
x=lca[x][i];
for(int i=NI;i>=0;i--) //不知道能不能正着循环，好像倒着优，反正记得倒着就好了
if(lca[x][i]!=lca[y][i]) //如果x跳2^i和y跳2^j没跳到一起就让他们跳
ans+=f[x][i]+f[y][i],
x=lca[x][i],y=lca[y][i];
return ans+f[x][0]+f[y][0]; //跳到LCA上去（每步跳的时候都要更新信息，而且要在跳之前更新信息哦~）
}
int main()
{
int a,b;
scanf("%d%d",&a,&b);
build(1,2,a);
build(1,3,b); //分别建1 2、1 3之间的边
dfs(1); //以1为根建树
printf("%d",ask(2,3)); //求解2 3到它们的LCA的距离和并输出
}
算法二十六、字典树
来自洛谷
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct node{
int str[26];
int sum;
}s[1000];
char str1[100];
int t=0,tot=0,ss=0;
bool f1;
void built()
{
t=0;
for(int i=0;i<strlen(str1);i++)
{
if(str1[i]=='-'){
f1=true;continue;
}
if(!s[t].str[str1[i]-'0'])
s[t].str[str1[i]-'0']=++tot;
t=s[t].str[str1[i]-'0'];
s[t].sum=str1[i]-'0';
}
}
int query()
{
int t=0;int s1=0;
for(int i=0;i<strlen(str1);i++)
{
if(str1[i]=='-') continue;
if(!s[t].str[str1[i]-'0']) return s1;
t=s[t].str[str1[i]-'0'];
s1=s1*10+s[t].sum;
}
return s1;
}
int main()
{
for(int i=1;i<=2;i++)
{
f1=false;
scanf("%s",str1);
built();
if(f1)
ss-=query();
else ss+=query();
}
printf("%d",ss);
return 0;
}
嘿嘿洛谷的没有啦~
算法二十七、Bellman-Ford
思路和别的最短路解法一样~
#include <bits/stdc++.h>
using namespace std;
int dis[50], u[50], v[50], w[50], n, m;
void bellman(int start) {
for (int i = 1;i <= n; i++) dis[i] = 0x3f3f3f3f;
dis[start] = 0;
for (int i = 1;i < n; i++)
for (int j = 1;j <= m; j++)
if (dis[v[j]] > dis[u[j]] + w[j]) dis[v[j]] = dis[u[j]] + w[j];
}
int main() {
n = 3; m = 2;
for (int i = 1;i <= m; i++) cin >> w[i], u[i] = i, v[i] = i + 1;
bellman(1);
printf("%d\n", dis[3]);
return 0;
}
算法二十八、可耻的打表
#include <bits/stdc++.h>
using namespace std;
int a, b; int main() {
scanf("%d%d", &a, &b);
if (a == 3 && b == 4) printf("7");
if (a == 45 && b == 55) printf("100");
if (a == 123 && b == 321) printf("444");
if (a == 91086199 && b == 18700332) printf("109786531");
if (a == 42267194 && b == 60645282) printf("102912476");
if (a == 69274392 && b == 10635835) printf("79910227");
if (a == 5710219 && b == 85140568) printf("90850787");
if (a == 75601477 && b == 24005804) printf("99607281");
if (a == 70597795 && b == 90383234) printf("160981029");
if (a == 82574652 && b == 22252146) printf("104826798");
return 0; //hh，这个len没加上return 0，还是我加的……
}
算法二十九、SPFA求最短路之SLF优化
呃呃呃就是加了个SLF优化而已
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 10;
const int INF = 0x7FFFFFFF;
int pre[maxn], dis[maxn], path[maxn];
bool vis[maxn];
int head[maxn], n, m;
int tot, cnt;
struct node {
int v, w, next;
} E[2 * maxn];
void add(int u, int v, int w) {
E[tot].v = v;
E[tot].w = w;
E[tot].next = head[u];
head[u] = tot++;
}
void init() {
tot = 0;
memset(vis, 0, sizeof vis);
memset(head, -1, sizeof head);
}
void spfa(int st) {
for (int i = 1;i <= n; i++) vis[i] = false, dis[i] = INF;
int now, next;
dis[st] = 0; vis[st] = 1;
deque<int> q;
q.push_back(st);
pre[st] = -1;
while(!q.empty()) {
now = q.front();
q.pop_front();
vis[now] = 0;
for (int i = head[now]; i != -1;i = E[i].next) {
next = E[i].v;
if(dis[next] > dis[now] + E[i].w) {
dis[next] = dis[now] + E[i].w;
pre[next] = now;
if(!vis[next]) {
vis[next] = 1;
if (q.empty() || dis[next] > dis[q.front()]) q.push_back(next);
else q.push_front(next);
}
}
}
}
}
void print(int x) {
if(pre[x] == -1) return;
print(pre[x]);
printf("%d ", x);
}
int main() {
init();
n = 3; m = 2;
int w;
for (int i = 1;i <= m; i++) {scanf("%d", &w); add(i, i + 1, w);}
spfa(1);
if(dis[n] == INF) puts("-1");
else printf("%d\n", dis[n]);
return 0;
}
算法三十、SPFA之LLL优化
#include<bits/stdc++.h>
#define MAXN 10010
#define MAXM 500010
#define MAX 2147483647
using namespace std;
int n, m, t, c = 1;
int head[MAXN], path[MAXN];
bool vis[MAXN];
struct node {
int next, to, w;
}a[MAXM << 1];
inline int relax (int u, int v, int w) {
if (path[v] > path[u] + w) {
path[v] = path[u] + w;
return 1;
}
return 0;
}
inline void add(int u, int v, int w) {
a[c].to = v;
a[c].w = w;
a[c].next = head[u];
head[u] = c++;
}
void spfa() {
int u, v, num = 0;
long long x = 0;
list<int> q;
for (int i = 1;i <= n; i++){path[i] = MAX; vis[i] = 0;}
path[1] = 0;
vis[1] = 1;
q.push_back(1);
num++;
while (!q.empty()) {
u = q.front();
q.pop_front();
num--; x -= path[u];
while (num && path[u] > x / num){
q.push_back(u);
u = q.front();
q.pop_front();
}
vis[u] = 0;
for (int i = head[u]; i ; i = a[i].next) {
v = a[i].to;
if (relax(u, v, a[i].w) && !vis[v]) {
vis[v] = 1;
if(!q.empty() && path[v] < path[q.front()]) q.push_front(v);
else q.push_back(v);
num++; x += path[v];
}
}
}
}
int main() {
n = 3; m = 2;
for (int i = 1;i <= m; i++) {
int w;
scanf("%d", &w);
add(i, i + 1, w);
}
spfa();
printf("%d\n", path[n]);
return 0;
}
算法三十一、SPFA之SLF+LLL优化算法
#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;
const int gg = 200000 + 11;
int head[gg], dis[gg], n, m, cnt;
bool vis[gg];
int sum, tot;
struct node{
int net, to, w;
} a[gg];
inline void add(int i, int j, int w) {
a[++cnt].to = j;
a[cnt].net = head[i];
a[cnt].w = w;
head[i] = cnt;
}
inline void spfa(int s) {
deque<int> q;
for (int i = 1;i <= n; i++) dis[i] = INF;
dis[s] = 0; vis[s] = 1;
q.push_back(s);
tot = 1;
while(!q.empty()) {
int u = q.front();
q.pop_front();
vis[u] = false;
tot--;
sum -= dis[u];
for (int i = head[u]; ~i ; i = a[i].net) {
int v = a[i].to;
if (dis[v] > dis[u] + a[i].w) {
dis[v] = dis[u] + a[i].w;
if(!vis[v]) {
vis[v] = 1;
if (q.empty() || dis[v] > dis[q.front()] || dis[v] * tot <= sum) q.push_back(v);
tot++;
sum += dis[v];
}
}
}
}
}
int main() {
memset(head, -1, sizeof head);
n = 3; m = 2;
for (int i = 1;i <= m; i++) {
int w = 0;
scanf("%d", &w);
add(i, i + 1, w);
}
spfa(1);
if (dis[n] == INF) puts("-1");
else printf("%d\n", dis[n]);
return 0;
}
算法三十二、只用一个变量跑A+B
把一个long long拆成两个int
指针啊！！！
#include<iostream>
using namespace std;
long long a;
int main() {
scanf("%d%d", (int*)(&a), (int*)(&a+1));
printf("%d\n", *((int*)&a) + *((int*)(&a+1)));
return 0;
}
算法三十三、矩阵乘法
#include<bits/stdc++.h>
using namespace std;
int a, b;
int x[2][2] = {
{0, 1},
{1, 1}
};
void mo(int f[]) {
int ans[2] = {0};
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++) ans[i] += f[j] * x[i][j];
for(int i = 0; i < 2; i++) f[i] = ans[i];
}
int main() {
cin >> a >> b;
int f[3] = {a, b};
mo(f);
cout << f[1];
return 0;
}
算法三十四、STL+dijkstra
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <climits>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#include <ctime>
#include <string>
#include <cstring>
using namespace std;
const int N=405;
struct Edge {
int v,w;
};
vector<Edge> edge[N*N];
int n;
int dis[N*N];
bool vis[N*N];
struct cmp {
bool operator()(int a,int b) {
return dis[a]>dis[b];
}
};
int Dijkstra(int start,int end)
{
priority_queue<int,vector<int>,cmp> dijQue;
memset(dis,-1,sizeof(dis));
memset(vis,0,sizeof(vis));
dijQue.push(start);
dis[start]=0;
while(!dijQue.empty()) {
int u=dijQue.top();
dijQue.pop();
vis[u]=0;
if(u==end)
break;
for(int i=0; i<edge[u].size(); i++) {
int v=edge[u][i].v;
if(dis[v]==-1 || dis[v]>dis[u]+edge[u][i].w) {
dis[v]=dis[u]+edge[u][i].w;
if(!vis[v]) {
vis[v]=true;
dijQue.push(v);
}
}
}
}
return dis[end];
}
int main()
{
int a,b;
scanf("%d%d",&a,&b);
Edge Qpush;
Qpush.v=1;
Qpush.w=a;
edge[0].push_back(Qpush);
Qpush.v=2;
Qpush.w=b;
edge[1].push_back(Qpush);
printf("%d",Dijkstra(0,2));
return 0;
}
算法三十五、数学表达式
#include <bits/stdc++.h>
using namespace std;
long long a, b;
int main() {
cin >> a >> b;
cout << a - b + (a * 2) - (a - b) - a + (a + (b - a)) << endl;
return 0;
}
算法三十六、define大法
#include <bits/stdc++.h>
#define ___ int
#define $$$ main
#define _$_$_ return
#define _ cin
#define $ cout
#define __ using
#define $$ namespace
#define o_o std
__ $$ o_o;
___ $$$(){
___ _$o$_,$o_o$;
_ >> _$o$_ >> $o_o$;
$ << _$o$_ + $o_o$;
_$_$_ 0;
}
算法三十七、压位高精度加法
奇怪的知识又增加了！
#include <bits/stdc++.h>
using namespace std;
const int mod = 100000000;
vector<int> add(vector<int> &A, vector<int> &B) {
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || i < B.size(); i++) {
if (i < A.size()) t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % mod);
t /= mod;
}
if (t) C.push_back(t);
return C;
}
int main() {
string a, b; cin >> a >> b;
vector<int> A, B, C;
for (int i = a.size() - 1, s = 0, j = 0, t = 1; i >= 0; i--) {
s += (a[i] - '0') * t;
j++; t *= 10;
if (j == 8 || i == 0) A.push_back(s), s = 0, j = 0, t = 1;
}
for (int i = b.size() - 1, s = 0, j = 0, t = 1; i >= 0; i--) {
s += (b[i] - '0') * t;
j++; t *= 10;
if (j == 8 || i == 0) B.push_back(s), s = 0, j = 0, t = 1;
}
C = add(A, B);
cout << C.back();
for (int i = C.size() - 2; i >= 0; i--) printf("%08d", C[i]);
return 0;
}
算法三十八、加一大堆东东……
听说手动开O3优化……
虽然好像没优化多少
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b; scanf("%d%d", &a, &b);
printf("%d", a + b);
return 0;
}
算法三十九、暴力枚举优化版
和算法六区别“不大”但是时间优化了300ms……
时间：$1567 ms$
就是在 $min(2 \times a, 2 \times b)$ 到 $max(2 \times a, 2 \times b)$ 之间枚举，效率高了“亿”点点
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b; scanf("%d%d", &a, &b);
for (int i = min(2 * a, 2 * b);i <= max(2 * a, 2 * b); i++)
if (a + b == i) {
printf("%d", i); //注意要输出i，不然如果输出a+b循环就没意义了……
return 0;
}
}
算法四十、矩阵DP
就是和方格取数之类的这些同样的思维~
#include <bits/stdc++.h>
using namespace std;
int a[110][110], n = 2;
int main() {
for (int i = 1;i <= n; i++)
for (int j = 1;j <= n; j++) scanf("%d", &a[i][j]);
for (int i = 1;i <= n; i++)
for (int j = 1;j <= n; j++)
if (max(a[i - 1][j], a[i][j - 1]) > -1) a[i][j] += max(a[i - 1][j], a[i][j - 1]);
printf("%d\n", a[n][n]);
return 0;
}
算法四十一、拖延时间大法
yyds!永远的拖延时间！
3176 ms天哪！
#include <algorithm>
//STL 通用算法
#include <bitset>
//STL 位集容器
#include <cctype>
//字符处理
#include <cerrno>
//定义错误码
#include <cfloat>
//浮点数处理
#include <ciso646>
//对应各种运算符的宏
#include <climits>
//定义各种数据类型最值的常量
#include <clocale>
//定义本地化函数
#include <cmath>
//定义数学函数
#include <complex>
//复数类
#include <csignal>
//信号机制支持
#include <csetjmp>
//异常处理支持
#include <cstdarg>
//不定参数列表支持
#include <cstddef>
//常用常量
#include <cstdio>
//定义输入／输出函数
#include <cstdlib>
//定义杂项函数及内存分配函数
#include <cstring>
//字符串处理
#include <ctime>
//定义关于时间的函数
#include <cwchar>
//宽字符处理及输入／输出
#include <cwctype>
//宽字符分类
#include <deque>
//STL 双端队列容器
#include <exception>
//异常处理类
#include <fstream>
//文件输入／输出
#include <functional>
//STL 定义运算函数（代替运算符）
#include <limits>
//定义各种数据类型最值常量
#include <list>
//STL 线性列表容器
#include <locale>
//本地化特定信息
#include <map>
//STL 映射容器
#include <memory>
//STL通过分配器进行的内存分配
#include <new>
//动态内存分配
#include <numeric>
//STL常用的数字操作
#include <iomanip>
//参数化输入／输出
#include <ios>
//基本输入／输出支持
#include <iosfwd>
//输入／输出系统使用的前置声明
#include <iostream>
//数据流输入／输出
#include <istream>
//基本输入流
#include <iterator>
//STL迭代器
#include <ostream>
//基本输出流
#include <queue>
//STL 队列容器
#include <set>
//STL 集合容器
#include <sstream>
//基于字符串的流
#include <stack>
//STL 堆栈容器
#include <stdexcept>
//标准异常类
#include <streambuf>
//底层输入／输出支持
#include <string>
//字符串类
#include <typeinfo>
//运行期间类型信息
#include <utility>
//STL 通用模板类
#include <valarray>
//对包含值的数组的操作
#include <vector>
//STL 动态数组容器
//头文件拖延编译时间（虽然不能拖延运行时间，但能拖一点编译时间也很不错了hh）
using namespace std;
int main(){
int a; int b; //不用int a, b;，拖延运行时间
cin >> a >> b; //cin拖延运行时间
int ans = 1 * 10000 / 10 / 10 / 10 / 10 * 5 * 2 / 10 - 1; //ans表达式拖延编译和运行时间
for (int i = 1;i <= a; i++) ans += 5, ans -= 4; //拖延时间
for (int i = 1;i <= b; i++) ans += 5, ans -= 4; //拖延时间
ans = ans - ans + ans + ans - ans; //表达式拖延时间
cout << ans << endl; //cout和多输出回车拖延时间
return 0;
}
算法四十二、极限卡点
卡到了9970ms……
#include <bits/stdc++.h>
using namespace std;
int st = clock();
int main() {
int a, b; scanf("%d%d", &a, &b);
while (clock() - st < 995000) {}
printf("%d", a + b);
return 0;
}
算法四十三、快读快写
#include<bits/stdc++.h>
using namespace std;
int read() {
int s = 0, f = 1;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') f = -1;
ch = getchar();
}
while(isdigit(ch)) {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
void write(int x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
return;
}
int main() {
int a, b; a = read(); b = read();
write(a + b);
return 0;
}
算法四十四、终极大杀器快读快写
#include<bits/stdc++.h>
using namespace std;
static char buf[100000], *pa = buf, *pd = buf;
#define gc pa == pd && (pd = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pd) ? EOF : *pa++
inline int read() {
register int x(0); register char c(gc);
while (c < '0' || c > '9') c = gc;
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = gc;
return x;
}
void write(int x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
return;
}
int main() {
int a, b; a = read(); b = read();
write(a + b);
return 0;
}
算法四十五、sort大大大大大大大大大法
sort yyds!
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main(){
n = 2;
for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
sort(a + 1, a + 1 + n);
int ans = 0;
for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
return 0;
}
算法四十六、冒泡排序
E……
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int a[MAXN], n;
int main(){
n = 2;
for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
for (int i = n;i > 1; i--)
for(int j = 1;j < i; j++)
if(a[j] > a[j + 1]) swap(a[j], a[j + 1]);
int ans = 0;
for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
return 0;
}
算法四十七、选择排序
………………
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int a[MAXN], n;
int main(){
n = 2;
for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
for (int i = 1;i < n; i++) {
int w = i, Min = a[i];
for (int j = i;j <= n; j++) if(Min > a[j]) w = j, Min = a[j]; //寻找🔎最小数和它的位置
swap(a[i], a[w]);
}
int ans = 0;
for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
return 0;
}
算法四十八、插入排序
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int a[MAXN], n;
int main(){
n = 2;
for (int i = 1;i <= n; i++) {
scanf("%d", &a[i]); int x = i - 1;
while(a[x] > a[x + 1] && x > 0) swap(a[x], a[x + 1]), x--;
}
int ans = 0;
for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
return 0;
}
算法四十九、希尔排序
azzzzzzzzzzzzzzzzzz
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main(){
n = 2;
for (int i = 0;i < n; i++) scanf("%d", &a[i]);
for (int step = n / 2; step > 0; step /= 2)
for (int i = 0;i < step; i++)
for (int j = i + step;j < n; j += step)
if(a[j] < a[j - step]) {
int temp = a[j];
int k = j - step;
while (k >= 0 && temp < a[k]) {
swap(a[k + step], a[k]);
k -= step;
}
}
int ans = 0;
for (int i = 0;i < n; i++) ans += a[i]; printf("%d ", ans);
return 0;
}
算法五十、归并排序
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN], T[MAXN];
void Mergesort(int l, int r) {
if (l == r) return; //区间内只有一个数，返回
int mid = l + r >> 1; //相当于(l + r) / 2
Mergesort(l, mid); //递归左半部分
Mergesort(mid + 1, r); //递归右半部分
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) //合并
if (a[i] <= a[j]) T[k++] = a[i++];
else T[k++] = a[j++];
while (i <= mid) T[k++] = a[i++];
while (j <= r) T[k++] = a[j++];
for (int q = l; q <= r; q++) a[q] = T[q]; //转移
}
int main() {
n = 2;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
Mergesort(1, n);
int ans = 0;
for (int i = 1; i <= n; i++) ans += a[i]; printf("%d", ans);
return 0;
}
算法五十一、快速排序
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
void quickSort(int l, int r) {
if (l >= r) return;
int i = l, j = r, base = a[l]; //base取最左边的数为基准数
while(i < j) {
while (a[j] >= base && i < j) j--;
while (a[i] <= base && i < j) i++;
if (i < j) swap(a[i], a[j]);
}
a[l] = a[i]; a[i] = base; //基准数归位
quickSort (l, i - 1); //递归左边
quickSort (i + 1, r); //递归右边
}
int main() {
n = 2;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
quickSort(1, n);
int ans = 0;
for (int i = 1; i <= n; i++) ans += a[i]; printf("%d", ans);
return 0;
}
算法五十二、堆排序
#include <bits/stdc++.h>
using namespace std;
int n;
const int MAXN = 1e8 + 10;
int h[MAXN], s;
void down(int u) {
int t = u; // t记录最小值
if (2 * u <= s && h[2 * u] < h[t]) t = 2 * u; // 左儿子
if (2 * u + 1 <= s && h[2 * u + 1] < h[t]) t = 2 * u + 1; // 右儿子
if (t != u) { //需要调整
swap(h[t], h[u]);
down(t); //递归
}
}
int main() {
n = 2;
for (int i = 1; i <= n; i ++) scanf("%d", &h[i]);
s = n;
for (int i = n / 2; i >= 1; i--) down(i); //初始化堆j
int ans = 0;
while (n--) {
ans += h[1];
h[1] = h[s]; s--;
down(1);
}
printf("%d", ans);
return 0;
}
算法五十三、计数排序
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
long long n, cnt[MAXN];
int main() {
n = 2; int x = 0, Max = -0x3f3f3f, Min = 0x3f3f3f; //初始化最大值和最小值
for (int i = 1; i <= n; i ++) {
scanf("%d", &x); cnt[x]++; //统计
Max = max(Max, x); Min = min(Min, x); //更新最大值和最小值
}
int ans = 0;
for (int i = Min;i <= Max; i++)
while(cnt[i]) cnt[i]--, ans += i;
printf("%d", ans);
return 0;
}
算法五十四、桶排序
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, Min = MAXN, Max = 0, sum[MAXN], ans;
bool f[45];
vector<int> bucket[45];//定义桶，这里定义40个桶
void insertsort(int s) {
for (int i = 0;i < bucket[s].size(); i++)
for (int j = i;j >= 1; j--) if(bucket[s][j - 1] > bucket[s][j]) swap(bucket[s][j], bucket[s][j - 1]);//这里是从小到大排序
for (int i = 0;i < bucket[s].size(); i++) ans += bucket[s][i];
}
void bucketsort() {
for (int i = 1;i <= n; i++)
bucket[int((sum[i] - Min) / ((Max - Min + 1) / 40.0))].push_back(sum[i]), f[int((sum[i] - Min) / ((Max - Min + 1) / 40.0))] = 1;//运用最大最小值来合理分配桶
for (int i = 0;i <= 40; i++) if(f[i]) insertsort(i); //如果当前桶有数值，则对桶内的数进行排序（这里用选择排序）
}
int main() {
n = 2;
for (int i = 1;i <= n; i++) {
scanf("%d", &sum[i]);
Min = min(Min, sum[i]), Max = max(Max, sum[i]); //为了能够合理利用空间，确保第一个桶和最后一个桶都有数，所以存储最大最小值
}
bucketsort(); printf("%d", ans);
return 0;
}
算法五十五、基数排序
#include <bits/stdc++.h>
using namespace std;
int maxbit(int data[], int n) {
int d = 1, p = 10; //d保存最大的位数
for (int i = 0;i < n; i++) while(data[i] >= p) p *= 10, d++;
return d;
}
void radixsort(int data[], int n) { //基数排序
int d = maxbit(data, n);
int tmp[n];
int cnt[15], i, j, k, radix = 1;
for (i = 1;i <= d; i++) { //进行d次排序
memset(cnt, 0, sizeof(cnt)); //清空计数器
for (j = 0;j < n; j++) {
k = (data[j] / radix) % 10;
cnt[k]++;
}
for (j = 1;j < 10; j++) cnt[j] += cnt[j - 1];
for (j = n - 1;j >= 0; j--) {
k = (data[j] / radix) % 10;
tmp[cnt[k] - 1] = data[j];
cnt[k]--;
}
for (j = 0;j < n; j++) data[j] = tmp[j];
radix *= 10;
}
}
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main(){
n = 2;
for (int i = 0;i < n; i++) scanf("%d", &a[i]);
radixsort(a, n);
int ans = 0;
for (int i = 0;i < n; i++) ans += a[i]; printf("%d", ans);
}
算法五十六、鸡尾酒排序
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main() {
n = 2;
for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
int cnt = 0;
while (1) {
int f = 0; cnt++;
if(cnt & 1)
for (int i = 1;i < n; i++) if(a[i] > a[i + 1]) swap(a[i], a[i + 1]), f = 1;
else
for (int i = n;i > 1; i--) if(a[i] < a[i - 1]) swap(a[i], a[i - 1]), f = 1;
if(!f) break;
}
int ans = 0;
for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
return 0;
}
算法五十七、二叉排序树排序
（怎么还是排序hh）
#include<bits/stdc++.h>
#define LL long long
#define INF 0x7FFFFFFF
using namespace std;
const int N = 1e8 + 10;
int n, idx, rt, ans;
int a[N], t[N];
int ch[N][2];
void insert(int &x, int val) {
if (!x) {
x = ++ idx;
t[x] = val;
return;
}
else {
if(val < t[x]) insert(ch[x][0], val);
else insert(ch[x][1], val);
}
}
void dfs(int x) { //中序遍历二叉排序树
if(!x) return;
dfs(ch[x][0]);
ans += t[x];
dfs(ch[x][1]);
}
int main() {
n = 2;
for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
for (int i = 1;i <= n; i++) insert(rt, a[i]);
dfs(rt); printf("%d", ans);
return 0;
}
算法五十八、侏儒排序
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main() {
n = 2;
for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
int s = 1;
while(s <= n) {
if(a[s - 1] <= a[s] || s == 0) s++;
else swap(a[s], a[s - 1]), s--;
}
int ans = 0;
for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
return 0;
}
算法五十九、猴子排序
（虽然在排序上理论会TLE……但是A+B还是能AC的……）
（排序终于结束了……hh）
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int check() {
for (int i = 1;i < n; i++) if(a[i] > a[i + 1]) return 0;
return 1;
}
int main() {
n = 2;
for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
while (1) {
random_shuffle(a + 1, a + 1 + n); //随机打乱数组的系统函数
if(check()) break;
}
int ans = 0;
for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
return 0;
}
算法六十、快速幂
#include<bits/stdc++.h>
using namespace std;
int qmi(int m, int k, int p) {
int res = 1 % p, t = m;
while (k) {
if (k & 1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}
int main() {
int a, b; scanf("%d%d", &a, &b);
printf("%d", qmi(a, 1, 100000010) + qmi(b, 1, 100000010));
return 0;
}
算法六十一、差分
#include <bits/stdc++.h>
using namespace std;
int n = 2, m = 5, b[10];
int main() {
for (int i = 1;i <= n; i++) {
int x; scanf("%d", &x);
b[1] += x; b[m + 1] -= x;
}
int ans = 0, x = 0;
for (int i = 1;i <= m; i++) {
x += b[i]; ans = max(ans, x);
}
printf("%d", ans);
return 0;
}
算法六十二、模拟人工计算
当然这注释是和人工计算最接近的hh
#include <bits/stdc++.h>
using namespace std;
int a, b;
int main() {
scanf("%d%d", &a, &b); //人眼看见数据
if (a == 0) {printf("%d", b); return 0;} //大脑瞬间“打表”被老师发现了，血量减少50……
if (b == 0) {printf("%d", a); return 0;} //大脑瞬间“打表”被老师发现了，血量减少50……
int f1 = 0, f2 = 0; //大脑申请了两个空间……（还好没炸掉）
if (a < 0) f1 = 1; //大脑正在判断，请勿打扰……
if (b < 0) f2 = 1; //大脑正在判断，请勿打扰……
a = abs(a); b = abs(b); //哇！大脑使用了去掉负号的大法！！！
int ans = 0; //大脑申请了一个空间
if (f1) ans -= a; //大脑正在艰难地判断着……
//大脑指挥手拿起笔在草稿纸上划来划去……
//大脑感到烦躁
//眼睛看到老师转了一下身子，立刻反馈给大脑
//大脑指挥手在计算器键盘上写下了算式……
//眼睛看到答案，反馈给大脑，大脑立刻指挥手关掉了计算器……
//眼睛看到老师转回来了
else ans += a; //大脑正在艰难地判断着……
if (f2) ans -= b;//大脑正在艰难地判断着……
//大脑指挥手拿起笔在草稿纸上划来划去……
//大脑感到烦躁
//眼睛看到老师转了一下身子，立刻反馈给大脑
//大脑指挥手在计算器键盘上写下了算式……
//眼睛看到答案，反馈给大脑，大脑立刻指挥手关掉了计算器……
//眼睛看到老师转回来了
else ans += b;//大脑正在艰难地判断着……
//眼睛观察到老师正在身后冷冷地看着……
//大脑感到紧张
//大脑让身体不由自主地颤抖起来
//大脑差点死机
//大脑复活
//立刻写下答案
printf("%d", ans);
//大脑又死机了……
//耳朵听到老师在叫自己起来
//大脑指挥身体起来了
//开始下一题……（下一个数据）
return 0;
}
算法六十三、二进制
额……好像有点不太正常
#include<bits/stdc++.h>
using namespace std;
int a, b, s, s1, i, na, nb;
int main() {
scanf("%d%d", &a, &b);
if (a <= 0) na = 1, a = abs(a);
while(a) {
if ((a & 1) != 0) s += pow(2, (a & 1) * i);
a >>= 1; i++;
}
i = 0;
if (na == 1) s = abs(s);
if (b <= 0) nb = 1, b = abs(b);
while(b) {
if ((b & 1) != 0) s1 += pow(2, (b & 1) * i);
b >>= 1; i++;
}
if (nb == 1) s1 = abs(s1);
printf("%d", s + s1);
return 0;
}
算法六十四、ST表
区间最小值加区间最大值 = A+B
#include <bits/stdc++.h>
using namespace std;
int n, a[10], st1[10][17], st2[10][17];
void ST_work1() {
for (int i = 1; i <= n; i++) st1[i][0] = a[i];
int t = log(n) / log(2) + 1;
for (int j = 1; j < t; j++) {
for (int i = 1; i <= n - (1 << j) + 1; i++)
st1[i][j] = max(st1[i][j - 1], st1[i + (1 << (j - 1))][j - 1]);
}
}
int ST_query1(int l, int r) {
int k = log(r - l + 1) / log(2);
return max(st1[l][k], st1[r - (1 << k) + 1][k]);
}
void ST_work2() {
for (int i = 1; i <= n; i++) st1[i][0] = a[i];
int t = log(n) / log(2) + 1;
for (int j = 1; j < t; j++) {
for (int i = 1; i <= n - (1 << j) + 1; i++)
st1[i][j] = min(st1[i][j - 1], st1[i + (1 << (j - 1))][j - 1]);
}
}
int ST_query2(int l, int r) {
int k = log(r - l + 1) / log(2);
return min(st1[l][k], st1[r - (1 << k) + 1][k]);
}
int main() {
n = 2;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
ST_work1(); int ans1 = ST_query1(1, 2);
ST_work2(); int ans2 = ST_query2(1, 2);
printf("%d", ans1 + ans2);
return 0;
}
算法六十五、01背包
#include <bits/stdc++.h>
using namespace std;
int c[1010], w[1010], dp[1010], n, m;
int main() {
n = 2; m = 2; //2个物体，背包容积2
for (int i = 1;i <= n; i++) c[1] = 1, scanf("%d", &w[i]); //设体积为1，读入价值
for (int i = 1;i <= n; i++)
for (int j = m; j >= c[i]; j--)
dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
printf ("%d\n", dp[m]);
return 0;
}
算法六十六、完全背包
#include <bits/stdc++.h>
using namespace std;
int c[1010], w[1010], dp[1010], n, m;
int main() {
n = 2; m = 3;
for (int i = 1;i <= n; i++) scanf("%d", &w[i]);
for (int i = 1;i <= n; i++)
for (int j = c[i]; j <= m; j++)
dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
printf ("%d\n", dp[m]);
return 0;
}
算法六十七、多重背包之暴力拆分法
#include <bits/stdc++.h>
using namespace std;
int c[110], w[110], s[110], dp[1010], n, m;
int main() {
n = 2; m = 2;
for (int i = 1;i <= n; i++) scanf("%d", &w[i]), c[i] = s[i] = 1;
for (int i = 1;i <= n; i++)
for (int x = 1;x <= s[i]; x++)
for (int j = m; j >= c[i]; j--)
dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
printf ("%d\n", dp[m]);
return 0;
}
算法六十八、多重背包之二进制拆分
#include <bits/stdc++.h>
using namespace std;
int n, m, v[10010], w[10010], f[2010];
int main() {
n = 2; m = 2;
int cnt = 0;
for (int i = 1; i <= n; i++) {
int a = 1, b, s = 1, k = 1; scanf("%d", &b);
while (k <= s) {
cnt++;
v[cnt] = a * k; w[cnt] = b * k;
s -= k; k <<= 1;
}
if (s > 0) {
cnt++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt;
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= v[i]; j -- )
f[j] = max(f[j], f[j - v[i]] + w[i]);
printf("%d\n", f[m]);
return 0;
}
算法六十九、二维费用背包问题
#include <bits/stdc++.h>
using namespace std;
int N, V, M;
int v[1010], m[1010], w[1010], f[1010][1010];
int main () {
N = V = M = 2;
for (int i = 1; i <= N; i++) scanf("%d", &w[i]), v[i] = m[i] = 1;
for (int i = 1; i <= N; i++)
for (int j = V; j >= v[i]; j--)
for (int k = M; k >= m[i]; k--)
f[j][k] = max(f[j - v[i]][k - m[i]] + w[i], f[j][k]);
printf("%d\n", f[V][M]);
return 0;
}
算法七十、分组背包问题
#include <bits/stdc++.h>
using namespace std;
int f[110][110], v[110][110], w[110][110], s[110];
int n, m, k;
int main() {
n = m = 2;
for (int i = 1; i <= n; i++) {
s[i] = 1;
for (int j = 0; j < s[i]; j++) scanf("%d", &w[i][j]), v[i][j] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j];
for (int k = 0; k < s[i]; k++)
if (j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
}
}
printf("%d", f[n][m]);
return 0;
}
算法七十一、有依赖的背包问题
#include <bits/stdc++.h>
using namespace std;
int n, m, v[110], w[110];
int h[110], e[110], ne[110], idx;
int f[110][110];
void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
void dfs(int u) {
for (int i = h[u]; ~i; i = ne[i]) { // 循环物品组
int son = e[i];
dfs(e[i]);
// 分组背包
for (int j = m - v[u]; j >= 0; j -- ) // 循环体积
for (int k = 0; k <= j; k ++ ) // 循环决策
f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
}
// 将物品u加进去
for (int i = m; i >= v[u]; i -- ) f[u][i] = f[u][i - v[u]] + w[u];
for (int i = 0; i < v[u]; i ++ ) f[u][i] = 0;
}
int main() {
n = m = 2;
memset(h, -1, sizeof h);
int root;
for (int i = 1; i <= n; i++) {
int p; v[i] = 1; scanf("%d", &w[i]);
if (i == 1) p = -1; else p = 1; //A+B中的特判
if (p == -1) root = i;
else add(p, i);
}
dfs(root);
printf("%d", f[root][m]);
return 0;
}
算法七十二、多重背包队列优化
#include <bits/stdc++.h>
using namespace std;
int n, m;
int f[20010], g[20010], q[20010];
int main() {
n = m = 2;
for (int i = 1; i <= n; i ++ ) {
int v = 1, w, s = 1; scanf("%d", &w);
memcpy(g, f, sizeof f);
for (int j = 0; j < v; j ++ ) {
int hh = 0, tt = -1;
for (int k = j; k <= m; k += v) {
if (hh <= tt && q[hh] < k - s * v) hh ++ ; //剔除超出长度元素
if (hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w); //更新当前答案
while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt -- ;
//维持单调性
//这里也可以这样写，更易理解
//while (hh <= tt && g[q[tt]] <= g[k] - (k - q[tt]) / v * w) tt -- ;
q[++tt] = k;
}
}
}
printf("%d", f[m]);
return 0;
}
算法七十三、$istream$_$iterator$
还是大佬们厉害，我没看懂……
#include <iostream>
#include <cstring>
#include <algorithm>
#include <numeric>
#include<iterator>
using namespace std;
int main()
{
istream_iterator<int> in(cin), eof;
cout << accumulate(in, eof ,0) << endl;
return 0;
}
算法七十四、进制转换
我本来想要十进制转二进制一个算法，十进制转三进制一个算法……然后发现甚至可以到十进制转$10^8$进制……
而且它们都属于进制转换，所以我决定直接写一个通用的进制转换程序。
然后随机进制转换，在那个进制下加法，再转化为十进制存储下来，如果所有的答案都一样，则输出这个答案。
我是不是很无聊
#include <bits/stdc++.h>
using namespace std;
int A[30], B[30], a, b;
int check(int mod) {
int x = a, y = b, ta = 0, tb = 0;
while (x) {
A[++ta] = x % mod;
x /= mod;
}
while (y) {
B[++tb] = y % mod;
y /= mod;
}
for (int i = 1; i <= max(ta, tb); i++) {
A[i] += B[i];
if (A[i] >= mod) A[i + 1] += A[i] / mod, A[i] %= mod;
}
if (A[ta + 1]) ta++;
int Ans = 0;
for (int i = ta; i > 0; i--) Ans = Ans * mod + A[i];
return Ans;
}
int main() {
scanf("%d%d", &a, &b);
int ans[100010];
for (int i = 1; i <= 100000; i++) {
srand((unsigned)time(NULL));
int o = (int) rand() % 1000000 + 2; //取随机进制
ans[i] = check(o);
}
bool f = 1;
for (int i = 2; i <= 100000; i++) if (ans[i] != ans[i - 1]) { f = 0; break; }
if (f) printf("%d\n", ans[1]);
else puts("老子不干了！WA就WA吧！一行WA上西天！"); //誓死不AC（逃）
return 0;
}
算法七十五、指针算法
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b;
cin>>a>>b;
int *c = &a, *d = &b, ans;
ans = *c + *d;
cout << ans << endl;
}
算法七十六、$vector$
#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int main() {
int x = 0;
while (cin>>x) v.push_back(x);
int ans = 0;
for (int i = 0; i < v.size(); i++) ans += v[i];
cout << ans;
return 0;
}
算法七十七、$queue$
#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int main() {
int x;
while (cin>>x) q.push(x);
int ans = 0;
while (q.size()) ans += q.front(), q.pop();
cout << ans;
return 0;
}
算法七十八、$deque$
#include <bits/stdc++.h>
using namespace std;
deque<int> a, b;
int main() {
int x;
while (cin>>x) a.push_front(x);
int ans = 0;
while (a.size()) ans += a.back(), b.push_back(a.back()), a.pop_back();
int res = 0;
while (b.size()) res += b.front(), b.pop_front();
if (ans == res) cout << (ans + res) / 2;
return 0;
}
算法七十九、$list$
#include <bits/stdc++.h>
using namespace std;
list<int> a, b;
int main() {
int x;
while (cin>>x) a.push_front(x);
int ans = 0;
while (a.size()) b.push_back(a.back()), ans += a.back(), a.pop_back();
int res = 0;
while (b.size()) res += b.front(), b.pop_front();
if (ans == res) cout << (ans + res) / 2;
return 0;
}
算法八十、$map$ 或 $unordered_map$
差不多就不再建一个了
#include <bits/stdc++.h>
using namespace std;
map<int, string> m;
int main() {
int x = 0;
while (cin>>x) m[x] = "Conan15是一只弱弱滴柯爱蒟蒻qwq";
int ans = 0;
for (auto iter = m.begin(); iter != m.end(); ++iter) {
ans += iter->first;
}
cout << ans;
return 0;
}
算法八十一、$set$ 或 $unordered_set$ 或 $multiset$
虽然都是 set
然后不想再新建了，同理。
#include <bits/stdc++.h>
using namespace std;
set<int> s;
int main() {
int x = 0;
while (cin>>x) s.insert(x);
int ans = 0;
for (auto iter = s.begin(); iter != s.end(); ++iter) {
ans += *iter;
}
cout << ans;
return 0;
}
算法八十二、$pair$
#include <bits/stdc++.h>
using namespace std;
int main() {
pair<int, int> a[110];
int x = 0, c = 0, t = 1;
while (cin>>x) {
if (c == 0) a[t].first = x, c = 1;
else a[t].second = x, t++, c = 0;
}
int ans = 0;
for (int i = 1; i <= 100; i++) {
ans += a[i].first + a[i].second;
}
cout << ans;
return 0;
}
算法八十三、$stack$
#include <bits/stdc++.h>
using namespace std;
stack<int> s;
int main() {
int x = 0;
while (cin>>x) s.push(x);
int ans = 0;
while (s.size()) ans += s.top(), s.pop();
cout << ans;
return 0;
}
算法八十四、$priority$_$queue$
#include <bits/stdc++.h>
using namespace std;
priority_queue<int> q;
int main() {
int x = 0;
while (cin>>x) q.push(x);
int ans = 0;
while (q.size()) ans += q.top(), q.pop();
cout << ans;
return 0;
}
算法八十五、不用变量
感谢@JcWing！
#include <iostream>
using namespace std;
int main ()
{
cin >> *new int () >> *new int ();
cout << *(new int () - 16) + *(new int () - 16);
return 0;
}
算法八十六、点分治
@Junounly Orz
#include<algorithm>
#include<cstring>
#include<bitset>
#include<cstdio>
#include<iostream>
#define ll long long
#define T(x) ((x)%mod)
using namespace std;
const int N=2e5+5,mod=1e9+7;
int n,a[N],root,mn,siz[N];
ll ans,cnt1[2],cnt2[2];
int h[N],e[N<<1],ne[N<<1],idx;
bool vis[N];
void add(int x,int y)
{
e[idx]=y,ne[idx]=h[x],h[x]=idx++;
}
void dfs1(int x,int fa,int num)
{
int mxp=0;
siz[x]=1;
for(int i=h[x];~i;i=ne[i])
{
int y=e[i];
if(y==fa||vis[y]) continue;
dfs1(y,x,num);
siz[x]+=siz[y];
mxp=max(mxp,siz[y]);
}
mxp=max(mxp,num-siz[x]);
if(mxp<mn) mn=mxp,root=x;
}
void dfs2(int x,int fa,int par,ll val)
{
cnt1[par]++,cnt2[par]=T(cnt2[par]+val);
for(int i=h[x];~i;i=ne[i])
{
int y=e[i];
if(y==fa||vis[y]) continue;
if(par) dfs2(y,x,0,val+a[y]);
else dfs2(y,x,1,val-a[y]);
}
}
int calc(int x,int par,ll val,ll p)
{
cnt1[0]=cnt2[0]=cnt1[1]=cnt2[1]=0;
dfs2(x,0,par,val);
cnt2[1]*=-1;
return T((cnt1[0]*cnt2[0]+cnt1[1]*cnt2[1])*2+
p*T(cnt1[0]*cnt1[0]-cnt1[1]*cnt1[1]));
}
void dfs3(int x,int num)
{
vis[x]=1;
ans=T(ans+calc(x,0,0,a[x]));
for(int i=h[x];~i;i=ne[i])
{
int y=e[i];
if(vis[y]) continue;
ans=T(ans-calc(y,1,-a[y],a[x]));
mn=1e9;
dfs1(y,0,siz[y]),dfs3(root,siz[y]);
}
}
int main()
{
memset(h,-1,sizeof(h));
int aa,bb;
cin>>aa>>bb;
a[1]=0,a[2]=aa,a[3]=bb;
add(1,2),add(2,1);
add(1,3),add(3,1);
mn=1e9,root=0;
dfs1(1,0,n),dfs3(root,n);
printf("%d\n",((ans+mod)%mod)/3);
return 0;
}
算法八十七、FHQ-Treap+队列优化空间+分治优化Build
@Junounly Orz
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,INF=0x3f3f3f3f;
struct BST
{
int l,r,x,siz,sum,res,pre,suf,chg;
bool f,cgd;
}a[N];
int n,m,idx,root,b[N];
queue<int> q;
int New(int x)
{
idx=q.front(),q.pop();
a[idx].l=a[idx].r=a[idx].cgd=a[idx].chg=0;
a[idx].x=a[idx].sum=a[idx].res=x;
a[idx].pre=a[idx].suf=max(x,0);
a[idx].siz=1;
return idx;
}
void PushUp(int u)
{
a[u].siz=a[a[u].l].siz+a[a[u].r].siz+1;
a[u].sum=a[u].x+a[a[u].l].sum+a[a[u].r].sum;
a[u].pre=max(a[a[u].l].pre,a[a[u].l].sum+a[u].x+a[a[u].r].pre);
a[u].suf=max(a[a[u].r].suf,a[a[u].r].sum+a[u].x+a[a[u].l].suf);
a[u].res=max(a[u].x,a[a[u].l].suf+a[u].x+a[a[u].r].pre);
if(a[u].l) a[u].res=max(a[u].res,a[a[u].l].res);
if(a[u].r) a[u].res=max(a[u].res,a[a[u].r].res);
}
void Reverse(int u)
{
swap(a[u].l,a[u].r);
swap(a[u].pre,a[u].suf);
a[u].f^=1;
}
void Change(int u,int x)
{
a[u].x=a[u].chg=x;
a[u].sum=a[u].siz*x;
a[u].pre=a[u].suf=max(a[u].sum,0);
a[u].res=max(x,a[u].sum);
a[u].cgd=1;
}
void PushDown(int u)
{
if(a[u].f)
{
Reverse(a[u].l);
Reverse(a[u].r);
a[u].f=0;
}
if(a[u].cgd)
{
Change(a[u].l,a[u].chg);
Change(a[u].r,a[u].chg);
a[u].cgd=0;
}
}
int Merge(int u,int v)
{
if(!u||!v) return u+v;
if(90000008%(a[u].siz+a[v].siz)<a[u].siz)
{
PushDown(u);
a[u].r=Merge(a[u].r,v);
PushUp(u);
return u;
}
PushDown(v);
a[v].l=Merge(u,a[v].l);
PushUp(v);
return v;
}
void Split(int u,int x,int &l,int &r)
{
if(!u)
{
l=r=0;
return;
}
PushDown(u);
if(a[a[u].l].siz<x) l=u,Split(a[u].r,x-a[a[u].l].siz-1,a[u].r,r);
else r=u,Split(a[u].l,x,l,a[u].l);
PushUp(u);
}
int Build(int l,int r)
{
if(l==r) return New(b[l]);
int mid=(l+r)>>1;
return Merge(Build(l,mid),Build(mid+1,r));
}
void Delete(int u)
{
if(!u) return;
q.push(u);
Delete(a[u].l);
Delete(a[u].r);
}
int main()
{
for(int i=1;i<=5e5;i++) q.push(i);
scanf("%d%d",&b[1],&b[2]);
root=Build(1,2);
int x=0,y=0,z=0;
Split(root,0,x,y);
Split(y,2,y,z);
a[y].f^=1;
root=Merge(x,Merge(y,z));
Split(root,0,x,y);
Split(y,2,y,z);
cout<<a[y].res<<endl;
root=Merge(x,Merge(y,z));
return 0;
}
算法八十八、文艺平衡树（FHQ-Treap实现）
@Junounly Orz
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,INF=(1ll<<31)-1;
struct BST
{
int l,r,x,p,siz;
bool f;
}a[N];
int n,m,idx,root;
int New(int x)
{
a[++idx].x=x;
a[idx].p=rand();
a[idx].siz=1;
return idx;
}
void PushUp(int u)
{
a[u].siz=a[a[u].l].siz+a[a[u].r].siz+1;
}
void PushDown(int u)
{
swap(a[u].l,a[u].r);
if(a[u].l) a[a[u].l].f^=1;
if(a[u].r) a[a[u].r].f^=1;
a[u].f=0;
}
int Merge(int u,int v)
{
if(!u||!v) return (u?u:v);
if(a[u].p<a[v].p)
{
if(a[u].f) PushDown(u);
a[u].r=Merge(a[u].r,v);
PushUp(u);
return u;
}
if(a[v].f) PushDown(v);
a[v].l=Merge(u,a[v].l);
PushUp(v);
return v;
}
void Split(int u,int x,int &l,int &r)
{
if(!u)
{
l=r=0;
return;
}
if(a[u].f) PushDown(u);
if(a[a[u].l].siz<x)
l=u,Split(a[u].r,x-a[a[u].l].siz-1,a[u].r,r);
else r=u,Split(a[u].l,x,l,a[u].l);
PushUp(u);
}
int main()
{
cin>>n>>m;
root=Merge(root,New(n));
root=Merge(root,New(m));
int x=0,y=0,z=0;
Split(root,0,x,y);
Split(y,2,y,z);
a[y].f^=1;
root=Merge(x,Merge(y,z));
Split(root,0,x,y);
Split(y,2,y,z);
cout<<a[1].x+a[2].x<<endl;
root=Merge(x,Merge(y,z));
return 0;
}
算法八十九、EXCRT
@lsz_ Orz
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL i,n,x,y;
LL a[3],b[3];
LL time_mod(LL a,LL b,LL p)
{
LL ans=0;
while(b)
{
if(b&1) ans=(ans+a)%p;
a=(a*2)%p;
b>>=1;
}
return ans;
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b)
{
x=1;
y=0;
return a;
}
LL gcd=exgcd(b,a%b,x,y),temp;
temp=x;
x=y;
y=temp-a/b*y;
return gcd;
}
LL calc()
{
LL x,y,ans=a[1],p=b[1];
for(int i=2;i<=n;i++)
{
LL at=p,bt=b[i],ct=(a[i]-ans%bt+bt)%bt,gcd=exgcd(at,bt,x,y),lm=bt/gcd;
x=time_mod(x,ct/gcd,lm);
ans+=x*p;
p*=lm;
ans=(ans%p+p)%p;
}
return (ans%p+p)%p;
}
int main()
{
n=2;
cin>>x>>y;
b[1]=x*2;
a[1]=(b[1]-x+y)%b[1];
b[2]=y*2;
a[2]=(b[2]-y+x)%b[2];
cout<<calc();
return 0;
}
算法九十、Treap（平衡树）
@Junounly Orz
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,INF=(1ll<<31)-1;
struct BST
{
int l,r,x,p,siz,cnt;
}a[N];
int q,p,idx,root;
int New(int x)
{
a[++idx].x=x;
a[idx].p=rand();
a[idx].siz=a[idx].cnt=1;
return idx;
}
void Update(int u)
{
a[u].siz=a[a[u].l].siz+a[a[u].r].siz+a[u].cnt;
}
void Build()
{
New(-INF),New(INF);
root=1,a[1].r=2;
Update(root);
}
int GetRank(int u,int x)
{
if(!u) return 0;
if(x==a[u].x) return a[a[u].l].siz;
if(x<a[u].x) return GetRank(a[u].l,x);
else return GetRank(a[u].r,x)+a[a[u].l].siz+a[u].cnt;
}
int GetValue(int u,int x)
{
if(!u) return INF;
if(a[a[u].l].siz>=x) return GetValue(a[u].l,x);
if(a[a[u].l].siz+a[u].cnt>=x) return a[u].x;
return GetValue(a[u].r,x-a[a[u].l].siz-a[u].cnt);
}
void zig(int &u)
{
int v=a[u].l;
a[u].l=a[v].r,a[v].r=u,u=v;
Update(a[u].r),Update(u);
}
void zag(int &u)
{
int v=a[u].r;
a[u].r=a[v].l,a[v].l=u,u=v;
Update(a[u].l),Update(u);
}
void Insert(int &u,int x)
{
if(!u)
{
u=New(x);
return;
}
if(x==a[u].x)
{
a[u].cnt++,Update(u);
return;
}
if(x<a[u].x)
{
Insert(a[u].l,x);
if(a[u].p<a[a[u].l].p)
zig(u);
}
else
{
Insert(a[u].r,x);
if(a[u].p<a[a[u].r].p)
zag(u);
}
Update(u);
}
int GetPrev(int u,int x,int res)
{
if(a[u].x>=x)
{
if(!a[u].l) return res;
return GetPrev(a[u].l,x,res);
}
if(!a[u].r) return a[u].x;
return GetPrev(a[u].r,x,a[u].x);
}
int GetNext(int u,int x,int res)
{
if(a[u].x<=x)
{
if(!a[u].r) return res;
return GetNext(a[u].r,x,res);
}
if(!a[u].l) return a[u].x;
return GetNext(a[u].l,x,a[u].x);
}
void Remove(int &u,int x)
{
if(!u) return;
if(x==a[u].x)
{
if(a[u].cnt>1)
{
a[u].cnt--,Update(u);
return;
}
if(a[u].l||a[u].r)
{
if(!a[u].r||a[a[u].l].p>a[a[u].r].p)
zig(u),Remove(a[u].r,x);
else zag(u),Remove(a[u].l,x);
Update(u);
return;
}
u=0;
return;
}
if(x<a[u].x) Remove(a[u].l,x);
else Remove(a[u].r,x);
Update(u);
}
int main()
{
cin>>q>>p;
if(q>p) swap(q,p);
Build();
Insert(root,q);Insert(root,p);
Remove(root,p);Insert(root,p);
cout<<(GetPrev(root,p,-INF)+GetNext(root,q,INF)+GetValue(root,GetRank(root,q)+1)+GetValue(root,GetRank(root,p)+1))/2<<endl;
return 0;
}
算法九十一、BST（二叉查找树）
@Junounly Orz
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,INF=(1ll<<31)-1;
struct BST
{
int l,r,x,siz,cnt;
}a[N];
int q,p,idx,root;
int New(int x)
{
a[++idx].x=x,a[idx].siz=a[idx].cnt=1;
return idx;
}
void Build()
{
a[++idx].x=-INF,a[++idx].x=INF;
root=1,a[1].r=2;
}
int GetRank(int u,int x)
{
if(!u) return 0;
if(x==a[u].x) return a[a[u].l].siz;
if(x<a[u].x) return GetRank(a[u].l,x);
else return GetRank(a[u].r,x)+a[a[u].l].siz+a[u].cnt;
}
int GetValue(int u,int x)
{
if(!u) return INF;
if(a[a[u].l].siz>=x) return GetValue(a[u].l,x);
if(a[a[u].l].siz+a[u].cnt<x) return GetValue(a[u].r,x-a[a[u].l].siz-a[u].cnt);
return a[u].x;
}
void Insert(int &u,int x)
{
if(!u)
{
u=New(x);
return;
}
a[u].siz++;
if(x==a[u].x)
{
a[u].cnt++;
return;
}
if(x<a[u].x) Insert(a[u].l,x);
else Insert(a[u].r,x);
}
int GetPrev(int u,int x,int res)
{
if(a[u].x>=x)
{
if(!a[u].l) return res;
return GetPrev(a[u].l,x,res);
}
if(!a[u].r) return a[u].x;
return GetPrev(a[u].r,x,a[u].x);
}
int GetNext(int u,int x,int res)
{
if(a[u].x<=x)
{
if(!a[u].r) return res;
return GetNext(a[u].r,x,res);
}
if(!a[u].l) return a[u].x;
return GetNext(a[u].l,x,a[u].x);
}
int main()
{
cin>>q>>p;
if(q>p) swap(q,p);
Build();
Insert(root,q);
Insert(root,p);
cout<<(GetPrev(root,p,-INF)+GetNext(root,q,INF)+GetValue(root,GetRank(root,q)+1)+GetValue(root,GetRank(root,p)+1))/2<<endl;
return 0;
}
算法九十二、Dijkstra 堆优化
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 1000010;
int head[N], ver[M], edge[M], nxt[M], d[N];
bool st[N];
int n, m, tot;
priority_queue< pair<int, int> > q;
void add(int x, int y, int z) {
ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
void dijkstra() {
memset(d, 0x3f3f3f3f, sizeof d);
memset(st, 0, sizeof st);
d[1] = 0;
q.push({0, 1});
while (q.size()) {
int x = q.top().second;
q.pop();
if (st[x]) continue;
st[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i], z = edge[i];
if (d[y] > d[x] + z) {
d[y] = d[x] + z;
q.push({-d[y], y});
}
}
}
}
int main() {
n = 3, m = 2;
for (int i =1 ; i <= m; i++) {
int x = i, y = i + 1, z;
scanf("%d", &z);
add(x, y, z);
}
dijkstra();
if (d[n] != 0x3f3f3f3f) cout<<d[n];
else puts("-1");
}
算法九十三、FFT
Orz @[acwingxyy]
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef struct complex
{
double a, b;
complex(double x = 0, double y = 0)
{
a = x, b = y;
}
complex operator + (const complex& t) const
{
return complex(a + t.a, b + t.b);
}
complex operator - (const complex& t) const
{
return complex(a - t.a, b - t.b);
}
complex operator * (const complex& t) const
{
return complex(a * t.a - b * t.b, a * t.b + b * t.a);
}
} cp;
const int N = 18;
const double pi = 2 * acos(-1);
char f[N], g[N], c[N];
int n, m, r[N];
cp a[N], w[N];
int log_2(int x)
{
int res = 0;
if (x & 0xffff0000) res += 16, x >>= 16;
if (x & 0xff00) res += 8, x >>= 8;
if (x & 0xf0) res += 4, x >>= 4;
if (x & 0xc) res += 2, x >>= 2;
if (x & 2) res ++ ;
return res;
}
void init()
{
m += n;
int bit = log_2(m);
n = 1 << bit + 1;
for (int i = 0; i < n; i ++ ) r[i] = r[i >> 1] >> 1 | (i & 1) << bit;
cp t(cos(pi / n), sin(pi / n));
w[0].a = 1;
for (int i = 1; i < n; i ++ ) w[i] = w[i - 1] * t;
}
void swap(cp& a, cp& b)
{
static cp t;
t = a, a = b, b = t;
}
void FFT(bool type)
{
for (int i = 0; i < n; i ++ ) if (i < r[i]) swap(a[i], a[r[i]]);
static cp x, y;
for (int len = 2; len <= n; len <<= 1)
for (int l = 0; l < n; l += len)
for (int i = 0, j = len >> 1; j < len; i ++ , j ++ )
{
x = a[l + i], y = w[n / len * i];
if (type) y = y * a[l + j];
else y = cp(y.a, -y.b) * a[l + j];
a[l + i] = x + y, a[l + j] = x - y;
}
}
int main()
{
scanf("%s\n%s", f, g);
n = strlen(f) - 1, m = strlen(g) - 1;
for (int i = n; ~i; i -- ) a[i].a = (double)(f[n - i] ^ 48);
for (int i = m; ~i; i -- ) a[i].b = (double)(g[m - i] ^ 48);
init();
FFT(1);
for (int i = 0; i < n; i ++ ) a[i] = a[i] * a[i];
FFT(0);
int t = 0;
for (int i = 0; i <= m; i ++ )
{
t += (int)(a[i].b / n / 2.0 + 0.5);
c[i] = t % 10 ^ 48, t /= 10;
}
int res = 0;
if (t) res = res * 10 + t;
for (int i = m; i >= 0; i -- ) res = res * 10 + (c[i] - '0');
n = strlen(f) - 1, m = strlen(g) - 1;
int a = 0, b = 0;
for (int i = 0; i <= n; i ++ ) a = a * 10 + (f[i] - '0');
for (int i = 0; i <= m; i ++ ) b = b * 10 + (g[i] - '0');
printf("%d\n", res - a * b + a + b);
return 0;
}
算法九十四、珂朵莉树
Orz @[acwingxyy]
#include <iostream>
#include <cstring>
#include <set>
using namespace std;
const int N = 35;
struct Node
{
int l, r;
mutable int v;
bool operator < (const Node& t) const
{
return l < t.l;
}
};
typedef set<Node>::iterator iter;
set<Node> ODT;
int a, b;
iter split(int x)
{
if (x > 2) return ODT.end();
auto it = -- ODT.upper_bound({x, 0, 0});
if (it -> l == x) return it;
int l = it -> l, r = it -> r, v = it -> v;
ODT.erase(it);
ODT.insert({l, x - 1, v});
return ODT.insert({x, r, v}).first;
}
void assign(int l, int r, int x)
{
auto itr = split(r + 1), itl = split(l);
ODT.erase(itl, itr);
ODT.insert({l, r, x});
}
int query(int l, int r)
{
static int cnt[N] = {0};
memset(cnt, 0, sizeof cnt);
auto itr = split(r + 1), itl = split(l); int res = 0;
for (; itl != itr; itl ++ ) res = res + ((itl -> r) - (itl -> l) + 1) * (itl -> v);
return res;
}
int main()
{
scanf("%d%d", &a, &b);
ODT.insert({1, 2, 0});
assign(1, 1, a), assign(2, 2, b);
printf("%d\n", query(1, 2));
return 0;
}
算法九十五、Johnson 全源最短路
@Junounly Orz
#include<bits/stdc++.h>
#define ll long long
#define PII pair<ll,ll>
using namespace std;
const int N=3005,INF=1e9;
int n,m,cnt[N];
ll pre[N],dis[N][N];
bool vis[N];
vector<PII> e[N];
void insert(int u,int v,int w){e[u].push_back({v,w});}
bool SPFA(int S)
{
queue<int> q;
fill(pre+1,pre+n+1,INF);memset(vis,0,sizeof(vis));
pre[S]=0;vis[S]=1;q.push(S);
while(q.size())
{
int x=q.front();q.pop();
vis[x]=0;
for(int i=0;i<e[x].size();i++)
{
int y=e[x][i].first,z=e[x][i].second;
if(pre[y]>pre[x]+z)
{
pre[y]=pre[x]+z;
if(!vis[y])
{
if(cnt[y]>=n) return 0;
vis[y]=1;cnt[y]++;q.push(y);
}
}
}
}
return 1;
}
void dijkstra(int S)
{
priority_queue<PII,vector<PII>,greater<PII> > q;
fill(dis[S]+1,dis[S]+n+1,1e9);memset(vis,0,sizeof(vis));
dis[S][S]=0;q.push({dis[S][S],S});
while(q.size())
{
ll x=q.top().second;q.pop();
if(vis[x]) continue;vis[x]=1;
for(ll i=0;i<e[x].size();i++)
{
ll y=e[x][i].first,z=e[x][i].second;
if(dis[S][x]+z<dis[S][y]) dis[S][y]=dis[S][x]+z,q.push({dis[S][y],y});
}
}
}
int main()
{
n=3;int X,Y;cin>>X>>Y;
insert(1,2,X);insert(2,3,Y);
for(int i=1;i<=n;i++) insert(0,i,0);
if(!SPFA(0)){puts("-1");return 0;}
e[0].clear();
for(int x=1;x<=n;x++)
for(int i=0;i<e[x].size();i++)
e[x][i].second+=pre[x]-pre[e[x][i].first];
for(int i=1;i<=n;i++)
{
dijkstra(i);
for(int j=1;j<=n;j++)
dis[i][j]-=(dis[i][j]!=INF)*(pre[i]-pre[j]);
}
cout<<dis[1][3]<<endl;
return 0;
}
算法九十六：冰茶寄（并查集）
stO @迎风飘扬
#include<bits/stdc++.h>
using namespace std;
int p[1001][2]={};
int find(int x,int s){
if(p[x][0]==x){
cout<<s+p[x][1];
return x;
}
p[x][0]=find(p[x][0],s+p[x][1]);
return p[x][0];
}
int main(){
for(int i=1;i<3;i++)cin>>p[i][1],p[i][0]=i;
p[1][0]=2;
find(1,0);
}
算法九十七、cdq 分治
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010, M = 200010;
int tr[N], ans[N];
struct Node {int a, b, c, s, res;} y[N], w[N];
void add(int x, int k) {while (x < M) {tr[x] += k; x += x & -x;}}
int query(int x) {int res = 0; while (x) {res += tr[x]; x -= x & -x;} return res;}
void merge(int l, int r) {
if (l >= r) return;
int mid = l + r >> 1;
merge(l, mid), merge(mid + 1, r);
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r)
if (y[i].b <= y[j].b) add(y[i].c, y[i].s), w[k ++ ] = y[i ++ ];
else y[j].res += query(y[j].c), w[k ++ ] = y[j ++ ];
while (i <= mid) add(y[i].c, y[i].s), w[k ++ ] = y[i ++ ];
while (j <= r) y[j].res += query(y[j].c), w[k ++ ] = y[j ++ ];
for (int i = l; i <= mid; i ++ ) add(y[i].c, -y[i].s);
for (int i = l; i <= r; i ++ ) y[i] = w[i];
}
int main() {
int a, b;
scanf("%d%d", &a, &b);
y[0] = {1, 1, 4, a};
y[1] = {5, 1, 4, b};
y[2] = {9, 9, 9};
merge(0, 2);
printf("%d\n", y[2].res);
return 0;
}
算法九十八、左偏树
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int val[N], l[N], r[N], dist[N];
bool cmp(int x, int y) {
if (val[x] != val[y]) return val[x] < val[y];
return x < y;
}
int merge(int x, int y) {
if (!x || !y) return x | y;
if (cmp(x, y)) swap(x, y);
r[x] = merge(r[x], y);
if (dist[l[x]] < dist[r[x]]) swap(l[x], r[x]);
dist[x] = dist[r[x]] + 1;
return x;
}
int main() {
int a, b, c, d, rt;
scanf("%d%d", &a, &b);
val[1] = a, val[2] = b, dist[1] = dist[2] = 1;
rt = merge(1, 2);
c = val[rt];
rt = merge(l[rt], r[rt]);
d = val[rt];
printf("%d", c + d);
return 0;
}
算法九十九、拉格朗日插值
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, mod = 998244353;
typedef long long LL;
int n, k;
int x[N], y[N];
int qmi(int a, int b, int p)
{
int res = 1 % p;
while (b)
{
if (b & 1) res = (LL)res * a % p;
b >>= 1;
a = (LL)a * a % p;
}
return res;
}
int main()
{
n = 2; cin >> x[1] >> x[2]; y[1] = x[1], y[2] = x[2];
k = x[1] + x[2];
LL res = 0;
for (int i = 1; i <= n; i ++ )
{
LL up = 1, down = 1;
for (int j = 1; j <= n; j ++ )
{
if (i == j) continue ;
up = up * (k - x[j]) % mod;
down = down * (x[i] - x[j]) % mod;
}
res = (res + (LL)y[i] * up % mod * qmi(down, mod - 2, mod) % mod) % mod;
}
printf("%lld\n", (res % mod + mod) % mod);
return 0;
}
算法一百、树链剖分！
特以此算法纪念我熟练掌握树剖板子！
有待补充
算法一百零一、树套树–线段树套平衡树
$O(n \log ^3 n)$
@acwing_xyy Orz
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, INF = 2147483647;
int n, m, w[N];
struct Node
{
int l, r;
int key, val;
int cnt, size;
};
struct Treap
{
Node tr[N * 20];
int idx;
int get_node(int key)
{
idx ++ ;
tr[idx].key = key;
tr[idx].val = rand();
tr[idx].cnt = tr[idx].size = 1;
return idx;
}
void pushup(int u)
{
tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
}
void zig(int &p)
{
int q = tr[p].l;
tr[p].l = tr[q].r, tr[q].r = p, p = q;
pushup(tr[p].r), pushup(p);
}
void zag(int &p)
{
int q = tr[p].r;
tr[p].r = tr[q].l, tr[q].l = p, p = q;
pushup(tr[p].l), pushup(p);
}
void insert(int &p, int key)
{
if (!p) p = get_node(key);
else
{
if (key == tr[p].key) tr[p].cnt ++ ;
else if (key < tr[p].key)
{
insert(tr[p].l, key);
if (tr[tr[p].l].val > tr[p].val) zig(p);
}
else
{
insert(tr[p].r, key);
if (tr[tr[p].r].val > tr[p].val) zag(p);
}
}
pushup(p);
}
void remove(int &p, int key)
{
if (!p) return ;
if (tr[p].key == key)
{
if (tr[p].cnt > 1) tr[p].cnt -- ;
else
{
if (tr[p].l || tr[p].r)
{
if (!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val)
{
zig(p);
remove(tr[p].r, key);
}
else
{
zag(p);
remove(tr[p].l, key);
}
}
else p = 0;
}
}
else key < tr[p].key ? remove(tr[p].l, key) : remove(tr[p].r, key);
if (p) pushup(p);
}
int get_rank_by_key(int p, int key)
{
if (!p) return 0;
else if (key == tr[p].key) return tr[tr[p].l].size;
else if (key < tr[p].key) return get_rank_by_key(tr[p].l, key);
return get_rank_by_key(tr[p].r, key) + tr[p].cnt + tr[tr[p].l].size;
}
int get_key_by_rank(int p, int rank) {
if (!p) return INF;
else if (tr[tr[p].l].size >= rank) return get_key_by_rank(tr[p].l, rank);
else if (tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;
return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}
int get_prev(int p, int key) {
if (!p) return -INF;
if (tr[p].key >= key) return get_prev(tr[p].l, key);
return max(tr[p].key, get_prev(tr[p].r, key));
}
int get_next(int p, int key) {
if (!p) return INF;
if (tr[p].key <= key) return get_next(tr[p].r, key);
return min(tr[p].key, get_next(tr[p].l, key));
}
void show(int u)
{
if (tr[u].l)
show(tr[u].l);
printf("%d %d\n", tr[u].key, tr[u].cnt);
if (tr[u].r)
show(tr[u].r);
}
}tree;
struct Segment
{
int l, r, root;
}tr[N * 8];
void build(int u, int l, int r)
{
tr[u] = {l, r};
for (int i = l; i <= r; i ++ ) tree.insert(tr[u].root, w[i]);
if (l != r)
{
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
}
void modify(int u, int x, int v)
{
tree.remove(tr[u].root, w[x]);
tree.insert(tr[u].root, v);
if (tr[u].l != tr[u].r)
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
}
}
int query_rank(int u, int l, int r, int k)
{
if (tr[u].l > r || tr[u].r < l) return 0;
if (tr[u].l >= l && tr[u].r <= r) return tree.get_rank_by_key(tr[u].root, k);
return query_rank(u << 1, l, r, k) + query_rank(u << 1 | 1, l, r, k);
}
int query_kth_number(int L, int R, int k)
{
int l = 0, r = 1e8;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (query_rank(1, L, R, mid) + 1 <= k) l = mid;
else r = mid - 1;
}
return r;
}
int query_prev(int u, int l, int r, int k)
{
if (tr[u].l > r || tr[u].r < l) return -INF;
if (tr[u].l >= l && tr[u].r <= r) return tree.get_prev(tr[u].root, k);
return max(query_prev(u << 1, l, r, k), query_prev(u << 1 | 1, l, r, k));
}
int query_next(int u, int l, int r, int k)
{
if (tr[u].l > r || tr[u].r < l) return INF;
if (tr[u].l >= l && tr[u].r <= r) return tree.get_next(tr[u].root, k);
return min(query_next(u << 1, l, r, k), query_next(u << 1 | 1, l, r, k));
}
int main()
{
n = 2;
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
build(1, 1, n); cout << query_kth_number(1, n, 1) + query_kth_number(1, n, 2);
return 0;
}
算法一百零二、FWT（快速沃尔什变换）
看不懂耶
stO @清风qwq
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long LL;
const int N = 1 << 17, P = 998244353;
int n;
int a[N], b[N], c[N];
int power(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = res * a % P;
a = a * a % P;
b >>= 1;
}
return res;
}
void XOR(int *a, int x) {
for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
for (int i = 0; i < n; i += o)
for (int j = 0; j < k; j ++ ) {
a[i + j] = (a[i + j] + a[i + j + k]) % P;
a[i + j + k] = (a[i + j] + P - a[i + j + k] + P - a[i + j + k]) % P;
a[i + j] = a[i + j] * x % P, a[i + j + k] = a[i + j + k] * x % P;
}
}
void get() {for (int i = 0; i < n; i ++ )c[i]=(LL)a[i]*b[i]%P;}
signed main() {
n = 2;
scanf("%d%d", &a[0], &a[1]);
b[0] = b[1] = 1;
XOR(a, 1), XOR(b, 1), get(), XOR(c,power(2, P - 2));
printf("%d\n", c[1]);
return 0;
}
算法一百零三、KM（二分图最大权完美匹配）
stO @清风qwq
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1010, INF = 0x3f3f3f3f;
int n, m;
int w[N][N];
int lx[N], ly[N], px[N], py[N], vx[N], vy[N];
int pre[N], slack[N];
void aug(int u) {
while (u) {
int k = px[pre[u]];
px[pre[u]] = u, py[u] = pre[u];
u = k;
}
}
void bfs(int s) {
memset(vx, 0, sizeof vx);
memset(vy, 0, sizeof vy);
memset(slack, 0x3f, sizeof slack);
queue<int> q;
q.push(s);
while (1) {
while (q.size()) {
int u = q.front();
vx[u] = 1;
q.pop();
for (int i = 1; i <= n; i ++ )
if (!vy[i]) {
if (lx[u] + ly[i] - w[u][i] < slack[i]) {
slack[i] = lx[u] + ly[i] - w[u][i];
pre[i] = u;
if (slack[i] == 0) {
vy[i] = 1;
if (!py[i]) {aug(i); return;}
else q.push(py[i]);
}
}
}
}
int d = INF;
for (int i = 1; i <= n; i ++ )
if (!vy[i])
d = min(d, slack[i]);
for (int i = 1; i <= n; i ++ ) {
if (vx[i]) lx[i] -= d;
if (vy[i]) ly[i] += d;
else slack[i] -= d;
}
for (int i = 1; i <= n; i ++ )
if (!vy[i] && slack[i] == 0) {
vy[i] = 1;
if (!py[i]) {aug(i); return;}
else q.push(py[i]);
}
}
}
signed main() {
n = 2, m = 2;
memset(w, 0x8f, sizeof w);
scanf("%lld%lld", &w[1][2], &w[2][1]);
lx[1] = w[1][2], lx[2] = w[2][1];
for (int i = 1; i <= n; i ++ ) bfs(i);
long long ans = 0;
for (int i = 1; i <= n; i ++ ) ans += lx[i] + ly[i];
printf("%lld\n", ans);
return 0;
}
算法一百零四、NTT
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m,tot,rev[1<<21];
int a[1<<21],b[1<<21];
vector<int> ans;
char s[1<<21];
int power(int a,int b)
{
int ans=1;
while (b) {
if (b&1) ans=1ll*ans*a%mod;
a=1ll*a*a%mod,b>>=1;
}
return ans;
}
void NTT(int *a,int type)
{
for (int i=0;i<tot;i++)
if (i<rev[i]) swap(a[i],a[rev[i] ]);
for (int mid=1;mid<tot;mid<<=1)
{
int g=power(3,(mod-1)/(mid<<1) );
for (int i=0;i<tot;i+=mid<<1)
{
int gk=1;
for (int j=0;j<mid;j++,gk=1ll*gk*g%mod) {
int x=a[i|j],y=1ll*gk*a[i|mid|j]%mod;
a[i|j]=(x+y)%mod,a[i|mid|j]=(x-y+mod)%mod;
}
}
}
if (~type) return;
int inv=power(tot,mod-2); reverse(a+1,a+tot);
for (int i=0;i<tot;i++) a[i]=1ll*a[i]*inv%mod;
}
int main()
{
scanf("%s",s),n=strlen(s)-1; for (int i=0;i<=n;i++) a[i]=s[n-i]&15;
scanf("%s",s),m=strlen(s)-1; for (int i=0;i<=m;i++) b[i]=s[m-i]&15;
tot=1; int l=-1; while (tot<=n+m) tot<<=1,l++;
for (int i=0;i<tot;i++) rev[i]=rev[i>>1]>>1|(i&1)<<l;
NTT(a,1),NTT(b,1); for (int i=0;i<tot;i++) a[i]=(a[i]+b[i])%mod; NTT(a,-1);
for (int i=0,t=0;i<=n+m||t;i++) t+=a[i],ans.push_back(t%10),t/=10;
while (!ans.back() ) ans.pop_back();
reverse(ans.begin(),ans.end() );
for (int x:ans) printf("%d",x);
return 0;
}
算法一百零五、可撤销并查集
#include<bits/stdc++.h>
using namespace std;
const int N=114514,M=1919810;
struct node{int u,v,fa,siz;}p[M];
int a[N],fa[M],siz[M],top;
int Find(int x){return (x==fa[x]?x:Find(fa[x]));}
void Union(int u,int v)
{
int x=Find(u),y=Find(v);
if(siz[x]>siz[y]) x^=y,y^=x,x^=y;
p[++top]={x,y,fa[x],siz[x]};
if(x!=y) fa[x]=y,siz[y]+=siz[x],siz[x]=0;
}
void Cancel()
{
node x=p[top--];
if(x.u!=x.v) fa[x.u]=x.fa,siz[x.u]=x.siz,siz[x.v]-=x.siz;
}
int main()
{
scanf("%d%d",&a[1],&a[2]);
for(int i=1;i<=2;i++) fa[i]=i,siz[i]=1;
Union(1,2);Union(1,3);Cancel();
printf("%d\n",a[1]+a[Find(1)]);
return 0;
}
由于即将超过 10w 字符的限制，在此重新开一个帖子保存接下来的算法awa~
$$\Huge 二帖传送门$$
搞了那么久，我们来个正常的吧……
满足某人的需求
观众们：你是认真的吗？
C代码
#include <stdio.h>
int main()
{
int a,b;
scanf("%d%d", &a, &b);
printf("%d\n", a + b);
return 0;
}
C++代码
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int a,b;
cin >> a >> b;
cout << a+b << endl;
return 0;
}
Pascal代码
var a, b: longint;
begin
readln(a,b);
writeln(a+b);
end.
Python代码
import sys
for line in sys.stdin:
print sum(map(int, line.split()))
Python2代码
s = raw_input().split()
print int(s[0]) + int(s[1])
Python3代码
print(sum(map(int, input().split())))
Java代码
import java.io.*;
import java.util.*;
public class Main {
public static void main(String args[]) throws Exception {
Scanner cin=new Scanner(System.in);
int a = cin.nextInt(), b = cin.nextInt();
System.out.println(a+b);
}
}
JavaScript代码（Node.js）
const fs = require('fs')
const data = fs.readFileSync('/dev/stdin')
const result = data.toString('ascii').trim().split(' ').map(x => parseInt(x)).reduce((a, b) => a + b, 0)
console.log(result)
process.exit() // 请注意必须在出口点处加入此行
Ruby代码
a, b = gets.split.map(&:to_i)
print a+b
PHP代码
<?php
$input = trim(file_get_contents("php://stdin"));
list($a, $b) = explode(' ', $input);
echo $a + $b;
Rust代码
use std::io;
fn main(){
let mut input=String::new();
io::stdin().read_line(&mut input).unwrap();
let mut s=input.trim().split(' ');
let a:i32=s.next().unwrap()
.parse().unwrap();
let b:i32=s.next().unwrap()
.parse().unwrap();
println!("{}",a+b);
}
Go代码
package main
import "fmt"
func main() {
var a, b int
fmt.Scanf("%d%d", &a, &b)
fmt.Println(a+b)
}
C# Mono代码
using System;
public class APlusB{
private static void Main(){
string[] input = Console.ReadLine().Split(' ');
Console.WriteLine(int.Parse(input[0]) + int.Parse(input[1]));
}
}
Visual Basic Mono代码
Imports System
Module APlusB
Sub Main()
Dim ins As String() = Console.ReadLine().Split(New Char(){" "c})
Console.WriteLine(Int(ins(0))+Int(ins(1)))
End Sub
End Module
Kotlin代码
fun main(args: Array<String>) {
val (a, b) = readLine()!!.split(' ').map(String::toInt)
println(a + b)
}
Haskell代码
main = do
[a, b] <- (map read . words) `fmap` getLine
print (a+b)
Scala代码
object Main extends App {
println(scala.io.StdIn.readLine().split(" ").map(_.toInt).sum)
}
Perl代码
my $in = <STDIN>;
chomp $in;
$in = [split /[\s,]+/, $in];
my $c = $in->[0] + $in->[1];
print "$c\n";
FoxPro代码
use
replace all c with a+b
谢谢你让我把所有算法复习了一遍
+1
我也是诶
# +1
+1
+1
+1
+1
+1
+1
+1
# 牛牪犇逼
#
哇，y总专属评论！38种的 O2 呢？？
哦，加了以后忘记更新了
假y总。。。
我当然知道，不然我加删除线干啥
我的意思是这人有被封的风险
嗯……如果他骚扰y总就更“好”了
23333
hh
就是比真y总多了个下划线
不是应该更牛逼嘛
这。。
我还遇见一个人，名字叫 hhyxc
这可太秀了
我给别人推荐AcWing,他说：“我知道，就是写A+B恶搞题解那个。”…
啊这哈哈哈哈哈哈哈哈哈哈哈哈哈
6
不是，yxc最帅啊
这也没恶搞题解啊
6
#define大法？？？！！！你是认真的？？？
看到这个方法直接笑出了声
那看看我的！
#C++代码：
define:宏定义，可以理解成简单替换。还可以宏定义函数：
注意多加
（括号）！19~21行的代码是一个
Lambda,可以理解为inline函数。Lambda可以有自己的参数：Lambda可以指定返回值类型。当然，
Lambda的[]也有用，但太复杂，就不讲了，大家可以看看资料包。Lambda资料包atexit：可以在程序结束时调用一个void函数。再介绍两个函数：
exit,_Exit：直接结束程序。最后两个🐥巧：
printf有返回值，正常情况是非零整数，所以可以：当
return有多个参数时，它只用最后一个：最后问问大家两个问题：
1：你们有什么压行🐥巧？
2：我发的题解只能被自己看见，有什么办法解决这个问题？
#The End~
###咯咯哒~（只因叫）
其实可以不用任何变量跑 $a + b$
用
new int ()就可以了还可以不用任何加法
代码给一下qwq
位运算吧，算法十五有了
眼瞎没看到
azqwq
new int的给一下代码
ok谢谢
为什么用这个1+2输出2
不是写了吗？
他写了我加上去的啊
牛逼
### Treap（平衡树）
前排支持！
谢谢！
c语言最短代码//应该是最短的
a,b;main(){scanf("%d%d",&a,&b);printf("%d",a+b);}### BST（二叉查找树）
能̸͍̫͙̥̭̈̏̄写҈͙͔͇̀̌́͂点̸̜̭͇̌͒͆̍̽注̸̥͖̠̞͖͗̈́̆释̷͕̠̤̒̅̓吗̴͚̖̱̞̙̃̋我̷͕̗̥̲̣̐͊͂看̵͉̰͙̖̉̓̔不̵̩̘̈́͐͑̈̈́懂҉̥͍̿̾？̶̪̠̟́͐͊？̶̪̩̮̙̉̌ͅ？̴̗̭́̋̆
what?
我用电脑看的，一堆乱码
这段文字根据百度搜索是“”写点，然而我可以看到在这段文字中还有一个“懂”字，所以您是说……
能写点注释吗我看不懂
是这样吗（抱歉，我也没时间写诶，马上冲刺毕业考了）
装吧你
谁都知道你把它粘在记事本上就能看得出来可是我不知道
能̸͍̫͙̥̭̈̏̄写҈͙͔͇̀̌́͂点̸̜̭͇̌͒͆̍̽注̸̥͖̠̞͖͗̈́̆释̷͕̠̤̒̅̓吗̴͚̖̱̞̙̃̋我̷͕̗̥̲̣̐͊͂看̵͉̰͙̖̉̓̔不̵̩̘̈́͐͑̈̈́懂҉̥͍̿̾？̶̪̠̟́͐͊？̶̪̩̮̙̉̌ͅ？̴̗̭́̋̆
+1
能̸͍̫͙̥̭̈̏̄写҈͙͔͇̀̌́͂点̸̜̭͇̌͒͆̍̽注̸̥͖̠̞͖͗̈́̆释̷͕̠̤̒̅̓吗̴͚̖̱̞̙̃̋我̷͕̗̥̲̣̐͊͂看̵͉̰͙̖̉̓̔不̵̩̘̈́͐͑̈̈́懂҉̥͍̿̾？̶̪̠̟́͐͊？̶̪̩̮̙̉̌ͅ？̴̗̭́̋̆
能写点注释嘛我看不懂
解密成功：能写点注释吗我看不懂？？？
能̸͍̫͙̥̭̈̏̄写҈͙͔͇̀̌́͂点̸̜̭͇̌͒͆̍̽注̸̥͖̠̞͖͗̈́̆释̷͕̠̤̒̅̓吗̴͚̖̱̞̙̃̋我̷͕̗̥̲̣̐͊͂看̵͉̰͙̖̉̓̔不̵̩̘̈́͐͑̈̈́懂҉̥͍̿̾？̶̪̠̟́͐͊？̶̪̩̮̙̉̌ͅ？̴̗̭́̋̆
̣đ̉́̃đ̣̉́đ̣̃́̉đ̃́̉đ́̃đ̉́̃đ́̉đ̃́̉đ́̃đ́̉đ̃đ̣̉́đ̃́đ̉̃đ̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̉đ̣̉́̃̉đ̣́̃đ̣̉́̃đ́̉đ̃́đ̣̉́̃đ̣̉́đ̃́̉đ́đ̃́đ̉́̃đ̉́̃đ̣́̉đ̃́đ̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̉̃đ̣̉́̃đ̉́̃đ́̉đ̃́đ́̉̃đ̉́̃đ̉́đ̣̃́̉̃́đ̉́̃đ̣̉́́́́́́́́́́́́́́́́́́́́́́́́́́́́́́́́́́́́́́́́́́́́́́́đ̣̉́̃đ̉́̃đ́̉̃́̉đ̃́̉đ̣̃́đ̉̃́đ̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣̣
能̸͍̫͙̥̭̈̏̄写҈͙͔͇̀̌́͂点̸̜̭͇̌͒͆̍̽注̸̥͖̠̞͖͗̈́̆释̷͕̠̤̒̅̓吗̴͚̖̱̞̙̃̋我̷͕̗̥̲̣̐͊͂看̵͉̰͙̖̉̓̔不̵̩̘̈́͐͑̈̈́懂҉̥͍̿̾？̶̪̠̟́͐͊？̶̪̩̮̙̉̌ͅ？̴̗̭́̋̆
小时候看这集吓哭了
长大后回来考古看呆了算法 $39$ 可以继续优化：
这样就不用老调 $max$ 函数了，省时。
嗯
istream_iteratoristream_iterator，用来从input steam读取数据。对，cin也用input steam读数据。accumulate再输出结果。istream_iterator（鸡）和它的孪生兄弟ostream_iterator（你）的资料包isteam_iterator资料包（太）osteam_iterator资料包（美）accumulateaccumulate是一个可以对指定区间内求和的函数。accumulate(起始迭代器,结束迭代器,初始值,自定义操作函数(默认为add))#if 0 + #endif注释法。模糊的说，#if 0 + #endif注释法的原理是跳过段，所以它可以保持代码原色。begin()和end()可以返回C array的起始迭代器和结束迭代器。现在，大家能看懂算法七十三了吗？
#The End~
(累死我了~)
可以单独开一个分享
我想开，但我不太会，教教我？
https://www.acwing.com/blog/
进去之后点击右边蓝色按钮“写分享”
然后就直接markdown代码写进去就好了，和这里一样
我会了，谢谢
### 点分治
### FHQ-Treap+队列优化空间+分治优化Build
### 文艺平衡树（FHQ-Treap实现）
补一种EXCRT的
扩展中国剩余定理？
对